The program solves a math problem by checking every possible group element of a free group "less than a certain length" for a certain property. In not-so-mathy: my elements are "strings" (not strings in the programming sense) of a's, b's, c's, ... (n letters) and -a's, -b's, -c's, so stuff like a b -a -b c b a -b -a -c. That one I just wrote has "length 10", and also has the property I want (which I'll get to later).

The O(lol) problem comes from the fact that a) I know the length of the shortest elements that will have the property I want grows exponentially with the number of generators (letters), and b) the number of elements of length d for n generators is (2n+1)^d, so if I want to check every element that's O( n^exp(n) ) ~= O(exp(exp(n))) since log(n) won't be very big (I'm expecting to only need to look at single digit n's). The first problem, a), is just a fact of life I think. The second problem, b), is the one I want some help with. Right now I'm just nesting O(exp(n)) for loops, which is what is making baby Jesus cry, but maybe there's a way around that.

My math problem is: consider a free group [imath]G[/imath] generated by [imath]a_1[/imath], [imath]a_2[/imath], ..., [imath]a_n[/imath]. Define [imath]\phi_i[/imath]: [imath]G \rightarrow G[/imath] as [imath]\phi_i(a_i) = \phi_i(a_i^{-1}) = e[/imath] (the identity), [imath]\phi_i(a_j) = a_j[/imath] for [imath]i \neq j[/imath] (and similarly for the inverses of generators), and [imath]\phi_i(gh) = \phi_i(g) \phi_i(h)[/imath] for all [imath]g, h[/imath] in [imath]G[/imath]. For example, [imath]\phi_2(a_1 a_2 a_1 a_2^{-1}) = a_1^2[/imath]. The problem is to find elements of this group [imath]g[/imath] such that [imath]g \neq e[/imath], but for every [imath]i[/imath], [imath]\phi_i(g) = e[/imath].

Here is my code (~300 lines in c++). I don't really expect anyone to go through it, but it's here for completeness. The only thing I do to try and optimize is to force every element to start with [imath]a_1[/imath], which cuts the time by 1/(2n+1) while only omitting solutions which are the same as other solutions up to renaming generators (which I don't care about). What I'm more interested in getting from this thread is just advice on how to avoid going through every element, or general advice on avoiding exp(n) nested for loops.

If you want to run the code, the shortest solutions for 2 generators are of length 4 (program runs instantly) and the shortest solutions for 3 generators are of length 10 (program takes about 10 minutes to run on my averageish laptop). The shortest solutions for 4 generators are of length 16 I think, and on my averageish laptop that would take about 60 years to run. The syntax is ./a.out <number of generators> <max length>, so ./a.out 2 4 or ./a.out 3 10 for instance.

Any help is much appreciated.

Code: Select all

`#include <stdio.h>`

#include <stdlib.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <string.h>

using namespace std;

/*

This program searches for solutions to an algebra problem.

Consider a free group G generated by a_1, a_2, ..., a_n. Define phi_i: G -> G as phi_i(a_i) = phi_i(a_i^-1) = e (the identity), phi_i(a_j) = a_j for i != j (and similarly for the inverses of generators), and phi_i(gh) = phi_i(g) phi_i(h) for all g, h in G. For example, phi_2(a_1 a_2 a_1 a_2^-1) = a_1^2. The problem is to find elements of this group g such that g != e, but for every i, phi_i(g) = e.

Throughout the program I use vector<int>s to represent these group elements. For example, the vector 1 2 1 -2 would represent a_1 a_2 a_1 a_2^-1. e is represented as 0. ("the vector 1 2 1 -2" is the vector with v[0] = 1, v[1] = 2, etc.)

*/

/******************************/

/*useful generic functions*/

/*sgn(x): 1 if x is positive, -1 if x is negative, 0 if x is 0*/

int sgn(int x)

{

if(x > 0)

return 1;

if(x < 0)

return -1;

return 0;

}

/*prints the entries of a vector in order*/

void printvec(vector<int> &v)

{

int counter;

for(counter = 0; counter < v.size(); counter++)

{

cout << v[counter] << " ";

}

}

/*true iff v1 and v2 are the same size and all their entries agree*/

bool vecssame(vector<int> &v1, vector<int> &v2)

{

int counter;

bool vecssame = true;

if(v1.size() != v2.size())

{

return false;

}

for(counter = 0; counter < v1.size(); counter++)

{

if(v1[counter] != v2[counter])

{

vecssame = false;

}

}

return vecssame;

}

/*checks if every entry of v is equal to i*/

bool allthisval(int i, vector<int> &v)

{

int counter;

bool allthisval = true;

for(counter = 0; counter < v.size(); counter++)

{

if(v[counter] != i)

{

allthisval = false;

}

}

return allthisval;

}

bool allthisval(bool i, vector<bool> &v)

{

int counter;

bool allthisval = true;

for(counter = 0; counter < v.size(); counter++)

{

if(v[counter] != i)

{

allthisval = false;

}

}

return allthisval;

}

/*******************************/

/*more specialized functions*/

/*simplifies an elt, canceling things with their inverses and omiting identities where appropriate*/

void simplify(vector<int> &v)

{

int counter = 0;

/*remove the identities*/

while(counter < v.size())

{

if(v[counter] == 0)

{

v.erase(v.begin()+counter);

}

else

{

counter++;

}

}

counter = 0;

/*cancel any elements next to their inverses*/

while(counter < ((int)v.size()-1))

{

if(v[counter] == -v[counter+1])

{

v.erase(v.begin()+counter+1);

v.erase(v.begin()+counter);

if(counter > 0)

{

counter--;

}

}

else

{

counter++;

}

}

}

/*turn every instance of +/- i to 0 in an elt.*/

void phi(int i, vector<int> &v)

{

int counter;

for(counter = 0; counter < v.size(); counter++)

{

if((v[counter] == i) || (v[counter] == -i))

{

v[counter] = 0;

}

}

}

/*Used to have arbirarily many nested for loops with the same range. v is a vector of counters, and every run through the loop the last one is incremented. Counting in base b and having each digit correspond to a counter will hit every possible combination of counters (in order) for each counter in the range 0..b-1. The range I want here is -b to b so the function is changed slightly to reflect that*/

void carry(int b, vector<int> &v)

{

int counter;

for(counter = (int)v.size()-1; counter > 0; counter--)

{

if(v[counter] > b)

{

v[counter] = -b; //in a normal carry this would be 0

v[counter-1]++;

}

}

}

/*To prevent getting a bunch of solutions which are the same up to renaming generators, I want all my solutions in "canonical form". I will say that an elt. is in canonical form if the generators and their inverses appear in order when reading from left to right (i.e. the first generator to appear is +/- 1, the second is +/- 2, etc.) and the first time each generator appears it's the generator, not the inverse.*/

void canonicalform(vector<int> &out, vector<int> &in, int numnails)

{

int counter = 0;

vector<bool> checked(numnails, false); //whether or not each generator has appeared in the elt. yet, reading left to right

vector<int> inverseorder(numnails); //inverseorder[n] = i means n was the ith generator to appear in the elt. from left to right, e.g. g = 4 2 1 3 has inverseorder = 3 2 4 1

int numchecked = 0; //number of 'true's in checked

vector<int> canonicalform; //stores the canonical form of in

vector<int> canonsgn(numnails); //to make sure that the first time a generator appears in the canonical form it's positive (i.e. the generator and not its inverse)

while(numchecked < numnails)

{

if(!checked[abs(in[counter])])

{

inverseorder[abs(in[counter])] = numchecked+1;

canonsgn[abs(in[counter])] = sgn(in[counter]);

checked[abs(in[counter])] = true;

numchecked++;

}

counter++;

}

for(counter = 0; counter < in.size(); counter++)

{

canonicalform.push_back(inverseorder[abs(in[counter])]*canonsgn[abs(in[counter])]*sgn(in[counter])); //produces what was advertised in the function description

}

out.swap(canonicalform); //this is essentially a return statement. Vectors can't be returned directly as far as I know.

}

/*once I have a bunch of solutions in canonical form I make a new vector of solutions which contains no duplicates*/

void weedsols(vector<vector<int> > &out, vector<vector<int> > &sols)

{

int counter1, counter2;

vector<vector<int> > weededsols; //sols with duplicates removed

bool newsol; //whether or not the solution at hand is new

for(counter1 = 0; counter1 < sols.size(); counter1++)

{

newsol = true;

for(counter2 = 0; counter2 < weededsols.size(); counter2++)

{

if(vecssame(sols[counter1], weededsols[counter2]))

{

newsol = false;

}

}

if(newsol)

{

weededsols.push_back(sols[counter1]);

}

}

out.swap(weededsols); //return statement

}

/*main has 4 steps: 1) it generates every possible group elt. of length < maxsize starting with 1 (since everything will be put into canonical form anyway). 2) it simplifies the group elt. If the elt. is not trivial 3) it checks if each phi_i makes it trivial. If they do then 4) the elt. is put into canonical form and stored in a solution vector.*/

main(int argc, char** argv)

{

if(argc != 3)

{

cout << "./<programname> <numnails> <maxsize>" << endl;

return -1;

}

vector<int> v; //group element. 1 is a_1, 2 is a_2, 0 is e, -1 is a_1^-1, etc.

vector<int> canonicalv; //canonical form of v

vector<vector<int> > canonicalsolutions; //nontrivial v's with phi_i(v) = e for all i, in canonical form

vector<vector<int> > distinctsolutions; //distinct entries in canonicalsolutions

int numnails = atoi(argv[1]);

int maxsize = atoi(argv[2]); //max size of v's

vector<int> counters(maxsize-1, -numnails); //to fill the v's

int i; //counter used in various places

vector<int> vcopy; //Because functions can't return vectors I instead have each phi modify the vector it was given. Because I want to put v into several phi'sI make a copy and give the phi's that instead in order to keep v intact.

vector<bool> phikills; //whether or not each phi makes v trivial. phikills[i] = true means phi_i(v) = e.

bool isgood; //if phikills[i] = true for all i, but v is not trivial itself, i.e. v is a solution.

while(!allthisval(numnails, counters)) //this is how the program knows where the effective for loop ends: when each counter = numnails (since each counter goes from -numnails to numnails in order)

{

v.clear();

v.push_back(1); //WLOG v[0] = 1

for(i = 0; i < counters.size(); i++)

{

v.push_back(counters[i]);

}

counters[counters.size()-1]++; //progressing through the effective for loop

carry(numnails, counters);

simplify(v);

if(!v.empty()) //v.empty() is true iff v is empty

{

phikills.clear();

for(i = 1; i <= numnails; i++)

{

vcopy = v;

phi(i, vcopy);

simplify(vcopy);

if(vcopy.empty())

{

phikills.push_back(true);

}

else

{

phikills.push_back(false);

}

}

isgood = allthisval(true, phikills);

if(isgood)

{

canonicalform(canonicalv, v, numnails);

canonicalsolutions.push_back(canonicalv);

}

}

}

weedsols(distinctsolutions, canonicalsolutions); //eliminate repeated solutions

//print results

cout << endl << "numnails: " << numnails << endl;

cout << "maxsize: " << maxsize << endl << endl;

cout << "solutions:" << endl;

for(i = 0; i < distinctsolutions.size(); i++)

{

printvec(distinctsolutions[i]);

cout << endl;

}

cout << endl;

return 0;

}