Instantly share code, notes, and snippets.

# Soubkia/Superpermutation BruteforcerSecret Created Mar 17, 2014

The superpermutation problem is best explained with an example. If I have 123 (or any three digit number for that matter), what is the smallest number which contains every permutation of 123 (231,312, 321, 321, 132). In this case the solution is known to be 123121321. However, for the case of 5 digits the solution is still unknown. I don't have …
 #include #include #include // Keeps track of the current max overlap and number int global_max = 0; std::vector > global_num; int factorial(int x, int result = 1) { if (x == 1) return result; else return factorial(x - 1, x * result); } // From: http://www.bearcave.com/random_hacks/permute.html // Simple print function void print(const int *v, const int size) { if (v != 0) { for (int i = 0; i < size; i++) { printf("%4d", v[i] ); } printf("\n"); } } void print_vect(std::vector > &v) { for (int i=0; i v) { for (int i=0; i > &v, int N) { for (int n=0; n temp; for (int p=0; p > perm) { int overlaps = 0; int quicklook = 0; // Look right at every point where permuatations are being combined for (int i=1; iglobal_max) { global_max = overlaps; global_num = perm; } //std::cout << "Total Overlaps: " << overlaps << std::endl; // For debuging } void make_possible_nums(int *Value, int N, int k, std::vector > &permutations) { static int level = -1; level = level+1; Value[k] = level; if (level == N) { std::vector > temp; for (int i=0; i<120; i++) { temp.push_back(permutations[Value[i]-1]); } // Find the effective size of Value find_size(temp); //print(Value, N); // For debuging } else { for (int i = 0; i < N; i++) { if (Value[i] == 0) { make_possible_nums(Value, N, i, permutations); } } } level = level-1; Value[k] = 0; } // From: http://www.bearcave.com/random_hacks/permute.html // Alexander Bogomolyn's unordered permutation algorithm void make_permutations_of_digits(int *Value, int N, int k, std::vector >& permutations, int &counter) { static int level = -1; level = level+1; Value[k] = level; for (int i=0; i<1; i++) { if (level == N) { for (int i = 0; i<5; i++) { permutations[counter][i] = Value[i]; } counter++; //print(Value, N); // For debuging } else { for (int i = 0; i < N; i++) { if (Value[i] == 0) { make_permutations_of_digits(Value, N, i, permutations, counter); } } } level = level-1; Value[k] = 0; } } // From: http://www.bearcave.com/random_hacks/permute.html // Alexander Bogomolyn's unordered permutation algorithm int main(int argc, const char * argv[]) { // Initilize to generate 5 digit permutations const int N = 5; int Value[N]; for (int i = 0; i < N; i++) { Value[i] = 0; } std::vector > permutations; make_empty_vect(permutations, N); // Counter to keep track of which branch of recursive loop I am on int counter = 0; make_permutations_of_digits(Value, N, 0, permutations, counter); std::cout << "Permutations to search:\n"; print_vect(permutations); const int N_ = 120; int Value_[N_]; for (int j=0; j