Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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 the computing power to run this to completion but this attempts to brute force the solution by turning this minimization problem into it's dual. It searches for the set of permutations lined up together such that the number of overlapping digits is maximized, however it must do this 120! times. Some areas this code could use some reworking include moving off the use of vectors in favor of int*'s and possibly switching to a different algorithm to calculate the permutations (there are algorithms known to be faster than the one currently being used). It's notable that the solution may not necessarily be unique.

View Superpermutation Bruteforcer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
#include <iostream>
#include <vector>
#include <stdio.h>
 
// Keeps track of the current max overlap and number
int global_max = 0;
std::vector<std::vector <int> > 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<std::vector<int> > &v)
{
for (int i=0; i<v.size(); i++)
{
for (int j=0; j<v[i].size(); j++)
{
std::cout << v[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << "Size: " << v.size() << std::endl;
}
 
void print_vector(std::vector<int> v)
{
for (int i=0; i<v.size(); i++)
std::cout << v[i] << " ";
std::cout << std::endl;
}
 
void make_empty_vect(std::vector <std::vector <int> > &v, int N)
{
for (int n=0; n<factorial(N); n++)
{
std::vector<int> temp;
for (int p=0; p<N; p++)
{
temp.push_back(0);
}
v.push_back(temp);
}
}
 
 
void find_size(std::vector<std::vector <int> > perm)
{
int overlaps = 0;
int quicklook = 0;
// Look right at every point where permuatations are being combined
for (int i=1; i<perm.size(); i++)
{
 
// for each digit we can combine the junction, increment the overlap
// we want to maximize overlap
while (perm[i][quicklook] == perm[i-1][4-quicklook])
{
overlaps++;
if (quicklook+1 == 5)
break;
else
{
//std::cout << "=======================================" << std::endl; // D
//std::cout << " Overlaps: " << overlaps << std::endl; // E
//print_vector(perm[i-1]); // B
//print_vector(perm[i]); // U
// // G
quicklook++;
}
}
quicklook = 0;
}
if (overlaps>global_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 <std::vector <int> > &permutations)
{
static int level = -1;
level = level+1; Value[k] = level;
if (level == N)
{
std::vector<std::vector<int> > 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 <std::vector <int> >& 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 <std::vector <int> > 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<N_; j++) {
Value_[j] = 0;
}
make_possible_nums(Value_, N_, 0, permutations);
std::cout << global_max << std::endl;
print_vect(global_num);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.