Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

cross-post from stack overflow

I have a list of numbers like {2,1,1,0} and I'd like to list all permutations of that list that are not equivalent under given symmetry group. So for instance if it was a dihedral group of order 4, result would be {{2, 1, 1, 0}, {2, 1, 0, 1}}. Is there a practical way to do this when the list is too large to generate all permutations?

Mathematica 8 seems to have a few group theory functions, but I don't have any group theory background, so any pointers are appreciated.

share|improve this question
    
you might benefit from using GAP. (see some examples here: math.jussieu.fr/~jmichel/gap3/htm/chap020.htm ) –  user1709 Dec 19 '10 at 10:28
    
Would you not also want {2,0,1,1}? –  Jack Schmidt Dec 19 '10 at 15:36
    
No, because of symmetry of the square -- mathematica-bits.blogspot.com/2010/12/… –  Yaroslav Bulatov Dec 19 '10 at 23:40

1 Answer 1

up vote 2 down vote accepted

To do this in (the free, open-source, group-theory software) GAP, you could use:

g := Group( (1,2)(3,4), (1,3)(2,4), (1,2,3,4) );;
d := PermutationsList( [2,1,1,0] );;
o := OrbitsDomain( g, d, Permuted );;
r := List( o, orbit -> Reversed( AsSet( orbit ) )[1] );

The first command defines a dihedral group (acting on the vertices of a square). The second command defines the domain on which the group will act: the set of all permutations of the list [2,1,1,0]. This list is constructed in memory, so this limits the size of the list. You can calculate the size of the list with:

NrPermutationsList([2,1,1,0]);

and look for a different method if the list is too long (up to ten thousand will be very quick, up to a million will be fine, after ten or twenty million you'll need to try something else). The third command sorts the domain into "orbits", the sets of equivalent permutations, with the group acting on the domain via the function "Permuted" which permutes the indices of a list. The fourth command asks for orbit representatives.

If g is small compared to d, then you are stuck. This is simply how hard the problem is. If g is reasonably large compared to d you can avoid computing d explicitly, using a transversal of an overgroup of g in the symmetric group.

However, try this version first. If you get to an example that doesn't work, post a specific group and list and I'll describe how the transversal works (it is often going to be slower, just more efficient in memory usage).


To work more specifically with your problem here are some GAP commands. For many partitions, GAP takes too long (so memory efficiency is not the problem). To get a random partition you could use:

x:=Random(Partitions(16));;
Append(x,ListWithIdenticalEntries(16-Size(x),0));;
x; NrPermutationsList(x);

I'll take:

x := [ 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0 ];

Now construct the symmetry group of the hypercube, the set of permutations of the partition, the orbits, and the orbit representatives as before:

g := WreathProductProductAction(SymmetricGroup(2),SymmetricGroup(4));;
d := PermutationsList( x );;
o := OrbitsDomain( g, d, Permuted );;
r := List( o, orbit -> Reversed( AsSet( orbit ) )[1] );;
Size( r );

After about a minute, it should print 1292. For 16 = 1+1+2+3+4+5 it has run for a day or so, and still isn't finished. No trouble with memory usage, it is just sifting through 3 million orderings. So, it is not practical for all the partitions, but for many it will work just fine.

share|improve this answer
    
Thanks for info, but that's similar to what I was already doing and the limitation was that I can't afford to generate a list of all permutations. The concrete problem is to get all ways of assigning 16 identical objects to vertices of a 4 dimensional cube. It's 300,540,195 ways before considering cube symmetries –  Yaroslav Bulatov Dec 19 '10 at 23:51
    
Well, the symmetry of the 4-dimensional cube only has 384 elements, so you are in the case where the output is very long: at least 750,000 ways after considering cube symmetries. –  Jack Schmidt Dec 20 '10 at 2:00
    
By the way, the code I gave computes the orderings of 2+2+2+2+2+2+2+1+1=16 in about a minute. There are 1292 orderings after cube symmetries, pretty close to Size(d)/Size(g). –  Jack Schmidt Dec 20 '10 at 2:04
    
Interesting...can you give the commands you used to get those 1292 orderings? –  Yaroslav Bulatov Dec 20 '10 at 20:52
    
ok, thanks, your example works and takes about a minute on my machine too –  Yaroslav Bulatov Dec 21 '10 at 0:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.