Skip to content

@Soubkia /Superpermutation Bruteforcer secret
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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 <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.