10-1100-cjeagleA1Code
From Drorbn
Jump to navigationJump to search
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;
}
