4
$\begingroup$

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.

  • 0
    No, because of symmetry of the square -- http://mathematica-bits.blogspot.com/2010/12/partitioning-integer-among-vertices-of.html2010-12-19

1 Answers 1

2

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.

  • 0
    ok, thanks, your example works and takes about a minute on my machine too2010-12-21