10-1100-cjeagleA1Code

This is the C++ source code I used to solve the MegaMinx. Aside from (BigInteger by Matt McCutcheon), which is a class in the public domain, it uses only standard C++. The algorithm is not terribly efficient (took about 6 hours to run), but it got the job done.

---

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include "BigIntegerLibrary.hh"             

using namespace std;

//sloppy code, but it made it easier to write
const int N = 132;
const int numGens = 12;

typedef vector<int> perm;

perm table[N][N];
perm ID;
perm blank;

/*to make it easier to input generating permutations
this algorithm takes in a list of an even number of numbers
and produces the permutation which sends a(i) to a(i+1) for each even i*/
perm permGen(vector<int> a){
     perm result(N);
     
     for(int i=0;i<N; i++){
             result[i] = i;
     }
     for(int i=0;i<a.size()-1;i+=2){
             result[a[i]]=a[i+1];
     }
     return result;
}

//an error-checking routine, making sure every element of the table is
//a valid permutation
bool isPerm(perm a){
     int checkr[N];
     for(int i=0;i<N;i++){
             for(int j=0;j<N;j++){
                     if(a[j] == i){checkr[i] = i;}
             }
     }
     
     for(int i=0; i<N;i++){
             if(checkr[i] != i){return false;}
     }
     return true;
}

//tests if two tables of permutations are the same
bool tableEqual(perm a[N][N], perm b[N][N]){
     for(int i=0; i<N; i++){
             for(int j=0; j<N; j++){
                     if(a[i][j] != b[i][j]){return false;}
             }
     }
     return true;
}

//Write one permutation to standard output
//Used for testing and error-checking
void permOutput(perm a){
     cout << "[";
     for(int i=0; i<N; i++){
             cout << a[i] << " ";
     }
     cout << "]";
}

//write the entire table to standard output
//this was useful in testing on small groups, but would not be suitable for
//groups as large as the MegaMinx
void tableOutput(){
     for(int i=0;i<N;i++){
             for(int j=0;j<N;j++){
                     permOutput(table[i][j]);
                     cout << "   ";
             }
             cout << endl;
     }
}

//find the pivot position of a permutation
int pivotPosition(perm s){
    for(int i=0; i<N; i++){
            if(s[i] != i) return i;
    }
    return -1;
}

//given permutations a and b, produce ab
perm mult(perm a, perm b){
     perm result(N);
     for(int i=0; i<N; i++){
        result[i] = a[b[i]];
     }

     return result;
}

//given a permutation a, produce a^{-1}
perm invert(perm a){
     perm result(N);
     for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
          if(a[j] == i){result[i] = j;}
        }
     }
     return result;
}

//the Feed algorithm from class
void Feed(perm s) {
     if(s == ID){return;}
     
     int pivot = pivotPosition(s);
     int value = s[pivot];
     if(table[pivot][value] == blank){
        table[pivot][value] = s;
        return;
     }
     
     Feed(mult(invert(table[pivot][value]), s));   
}

//compute the product of the sizes of the columns in the table
BigInteger groupOrder(){
     BigInteger result = 1;
     BigInteger colSize[N];
     for(int i=0; i<N; i++){
             colSize[i] = 0;
             for(int j=0;j<N;j++){
                     if(table[i][j] != blank){colSize[i] = colSize[i]+1;}
             }
     }
     
     for(int i=0; i<N; i++){
             result = result * colSize[i];
     }
     
     return result;
}
           
int main(int argc, char *argv[])
{
    ofstream outputFile;
    outputFile.open("megaminx.txt");
    
    outputFile << "MegaMinx" << endl << endl;
    //start by initializing the two constant permutations - blank and identity.
    //we make blank and invalid permutation for easier error-checking
    for(int i=0; i<N; i++){
            ID.push_back(i);
            blank.push_back(-1);
    }

    perm generators[numGens];

/*Generators come from rotating the marked face counterclockwise*/
  int gens[numGens][50] = {
      {3,1,10,3,0,10,7,0,1,7,6,2,9,6,8,9,4,8,2,4,17,55,14,56,11,57,55,46,56,49,57,53,46,101,49,104,53,108,101,110,104,111,108,112,110,17,111,14,112,11},                                         /*orange*/
      {20,13,21,20,17,21,11,17,13,11,19,16,18,19,14,18,12,14,16,12,112,72,115,69,119,66,72,28,69,25,66,22,28,61,25,58,22,55,61,3,58,6,55,10,3,112,6,115,10,119},                                 /*grey*/
      {31,24,32,31,28,32,22,28,24,22,27,23,30,27,29,30,25,29,23,25,66,77,67,78,68,79,77,39,78,36,79,33,39,65,36,62,33,61,65,13,62,16,61,20,13,66,16,67,20,68},                                   /*red*/
      {35,33,42,35,43,42,39,43,33,39,38,34,41,38,40,41,36,40,34,36,79,88,82,89,86,90,88,50,89,47,90,44,50,64,47,63,44,65,64,24,63,27,65,31,24,79,27,82,31,86},                                   /*light blue*/
      {46,44,53,46,54,53,50,54,44,50,49,45,52,49,51,52,47,51,45,47,90,99,93,100,97,101,99,7,100,4,101,1,7,57,4,60,1,64,57,35,60,38,64,42,35,90,38,93,42,97},                                     /*light brown*/
      {57,55,64,57,65,64,61,65,55,61,60,56,63,60,62,63,58,62,56,58,22,33,23,34,24,35,33,44,34,45,35,46,44,1,45,2,46,3,1,11,2,12,3,13,11,22,12,23,13,24},                                         /*purple*/
      {68,66,75,68,76,75,72,76,66,72,71,67,74,71,73,74,69,73,67,69,119,127,118,124,120,121,127,83,124,80,121,77,83,32,80,29,77,28,32,20,29,19,28,21,20,119,19,118,21,120},                       /*light green*/
      {86,79,87,86,83,87,77,83,79,77,82,78,85,82,84,85,80,84,78,80,121,94,122,91,123,88,94,43,91,40,88,39,43,31,40,30,39,32,31,68,30,71,32,75,68,121,71,122,75,123},                             /*dark brown*/
      {97,90,98,97,94,98,88,94,90,88,93,89,96,93,95,96,91,95,89,91,123,105,126,102,130,99,105,54,102,51,99,50,54,42,51,41,50,43,42,86,41,85,43,87,86,123,85,126,87,130},                         /*pink*/
      {108,101,109,108,105,109,99,105,101,99,104,100,107,104,106,107,102,106,100,102,130,116,129,113,131,110,116,0,113,8,110,7,0,53,8,52,7,54,53,97,52,96,54,98,97,130,96,129,98,131},           /*dark green*/
      {119,112,120,119,116,120,110,116,112,110,115,111,118,115,117,118,113,117,111,113,131,76,128,73,127,72,76,21,73,18,72,17,21,10,18,9,17,0,10,108,9,107,0,109,108,131,107,128,109,127},       /*dark blue*/
      {123,121,130,123,131,130,127,131,121,127,122,124,126,122,129,126,128,129,124,128,120,109,117,106,116,105,109,98,106,95,105,94,98,87,95,84,94,83,87,75,84,74,83,76,75,120,74,117,76,116}    /*magenta*/
  };
  
  //construct the actual generators from the above list
  for(int i=0;i<numGens; i++){
          generators[i] = permGen(vector<int>(gens[i], gens[i]+50));
  }
  
  //prepare a blank table
    for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                    table[i][j] = blank;
            }
    }
            
    //set the diagonal of the table to be the identity permutation
    for(int i=0; i<N; i++){
             table[i][i] = ID;
    }
    
    //write out the complete list of generators
    outputFile << "The generating permutations are: " << endl;
    for(int i=0;i<numGens;i++){
            outputFile << "[";
            for(int j=0; j<N; j++){
                    outputFile << generators[i][j] << " ";
            }
            outputFile << "]" << endl;
    }
    
    //Feed the generators into the table
    for(int i=0; i<numGens; i++){
            Feed(generators[i]);
    }

    perm tableCopy[N][N];
    
    do{
       //put a copy of table in tableCopy, so we can check if anything changed
        for(int i=0; i<N; i++){
            for(int j=0;j<N;j++){
                    tableCopy[i][j] = perm(table[i][j]);
            }
        }
        
        //check each pair of indices.  Every time we find (i,j) and (k,l) such that
        //table[i][j] and table[k][l] have entries, we feed the product of those entries
        for(int i=0;i<N;i++){
                for(int j=0; j<N; j++){
                        if(table[i][j] != blank){
                                       for(int k=0;k<N;k++){
                                               for(int l=0;l<N;l++){
                                                       if(table[k][l] != blank){
                                                                      Feed(mult(table[i][j], table[k][l]));
                                                       }
                                               }
                                       }
                        }
                }
        }
        //keep on going until nothing changes
    }while(!tableEqual(tableCopy, table));    
    
    //now the size of G is the product of the sizes of the columns.
    BigInteger orderOfGroup = groupOrder();
    outputFile << endl << endl << "The order of the subgroup of S_132 generated by the above is: " << orderOfGroup;
    outputFile.close();
    return 0;
}