HyperCube permutation

[Afshord]

Hi everybody,
I faced with a mathematical problem. I know completely the problem, I found its computational complexity, and I have written several programs, but non of them can solve the problem in general!

The problem is special kind of permutation, in the other words a permutation with some restrictions.

The problem: we want to find all possible permutations of a hypercube at dimensions 2,3, ..., 10, with keeping all neighbors together. for example in dimension two, we have a square abcd. a is neighbors of b and d, b is neighbors of a and c, c is neighbors of b and d, and d is neighbors of c and a. To obtain all possible permutations with keeping all neighbors together, we can rotate square 4 times. Then obtain its mirror and also rotate it, 4 times. The possible states will be:

abcd
dabc
cdab
bcda
dcba
adcb
badc
cbad

I found the number of all possible states with the mentioned condition which it will be |V| * d(v)!.
It means the number of vertices multiply factorial of degree of a vertex.
For example for a hypercube of dimension 2, number of possible states will be 4 * 2! = 8.
For a hypercube of dimension 3, number of possible states will be 8 * 3! = 48.

I think it will be easy if we can find a recursive approach.
Thanks for a person that he/she can suggest an algorithm or C++ code to solve this problem.

[Niven]

Are you trying to find the permutations themselves or just the number of permutations? If it's the latter (correct me if I'm wrong) then shouldn't the number of vertices just be 2^d where d is the dimension? So for dimension 10, it would be 2^10 * 10! (using your equation). If it's the former, then you will have to print out a lot of combinations for the higher dimensions (doing some estimation in my head I figure that 10 dimensions would have around 2.7 million combinations but I could be wrong). I may be wrong though; I don't fully understand the problem so I could've just wrote gibberish there for all I know.

[Afshord]

I want to find the permutations themselves. I want to use the results in the other program. As I have analysed, I think I will need at most the rank 7 in practice.

For dimension 10, the number of combinations will be more than 3.7 milliard!

[mik2718]

You want the symmetry group of the hypercube as a set of permutations.

Your formula gives 16x4! = 384 as the number of symmetries of the 4 dimensional hypercube - which is correct. So the formula looks OK.

I have to admit to using brute force methods in my 4D experiments so I am not an expert. But maybe you can generate these groups as combinations of a small set of generating elements.

This link is about doing something similar to what you want. To go from the rotation group to the full symmetry group you just need to add one reflection into the generator set (doubling the number of permutations)

http://math.stackexchange.com/questions/15174/how-to-get-group-of-hypercube-rotations-as-a-subgroup-of-symmetric-group

[Afshord]

But the computational complexity of the symmetry group is n!.
Please notice that for 4-dimension hypercube all possible permutations is 16!. I wrote a program to find all possible solutions among the all permutations. In fact I used the brute force algorithm, but in my computer it is needed approximately 41 day to found them! I need an smart algorithm.

I found the mentioned formula by myself and I have a mathematical proof for it, but I think it is not needed to declare it.

[mik2718]

Here is an idea - walk your way up the dimensions. For example starting with the 2D cube (a square we have)

abcd
dabc
cdab
bcda
dcba
adcb
badc
cbad

imagine this as one face of the 3D cube, call the other vertices e,f,g,h. We can straight away write down 8 symmetries for the 3D cube

abcd efgh
dabc hefg
cdab ghef
bcda fghe
dcba hgfe
adcb ehgf
badc fehg
cbad gfeh

If we have a symmetry of the 3D cube that is not in this set we combine it with each of these to give another 8 symmetries. To get all 48 3D cube symmetries we need to find 3 symmetries not in this set and combine.

Having done this the same process is repeated, using the 3D symmetries found so far to represent one cell of the 4D cube and duplicating the pattern to the other 8 vertices. Giving 48 of the 384 symmetries of the 4D cube. Now we need 8 symmetries not in the set of 48 to combine with it and give the full symmetry group

Continue in this way.

[Afshord]

Thanks a lot!
I wrote the program down in a special way..