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:
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.
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.
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)
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.
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