# Group Acting on a Set

Say I have a list $V$ (or a set $V$; either would be fine) of 5-tuples; e.g.,

V = [(0,1,1,0,0), (1,0,0,1,1), (0,0,0,1,0)].


Is there a pre-defined function in Sage to create a list $W$ of all 5-tuples generated when the group $S_5$ of permutations of ${1,2,3,4,5}$ acts of $V$? If not, is there a relatively quick way that I could go about this?

edit retag close merge delete

Sort by ยป oldest newest most voted

If you want the whole group of permutations act on your set (not a subgroup, in which case you should use Sage's PermutationGroup), i would suggest to use the itertools Python module which is pretty optimized and remains available even if you do not use Sage:

sage: from itertools import permutations
sage: list(permutations((0,1,1,0,0)))
[(0, 1, 1, 0, 0),
(0, 1, 1, 0, 0),
(0, 1, 0, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 1, 0),
...


Note the repetitions due to the fact that your vector also contains repetitions

So you want to apply this on each tuple you can think of list comprehension:

sage: [list(permutations(v)) for v in V]
[[(0, 1, 1, 0, 0),
(0, 1, 1, 0, 0),
(0, 1, 0, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 1, 0),
...
(0, 0, 1, 1, 0),
(0, 0, 1, 0, 1),
(0, 0, 1, 1, 0)],
[(0, 0, 0, 1, 0),
(0, 0, 0, 0, 1),
...
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 0)]]


So what you get is a list of lists (one for each vector). So you have to flatten this list of lists of tuples into a list of tuples:

sage: flatten([list(permutations(v)) for v in V], max_level=1)
[(0, 1, 1, 0, 0),
(0, 1, 1, 0, 0),
(0, 1, 0, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 1, 0, 0),
...


If you want to avoid the repetitions, you can make a set:

sage: set(flatten([list(permutations(v)) for v in V], max_level=1))
{(0, 0, 0, 0, 1),
(0, 0, 0, 1, 0),
(0, 0, 0, 1, 1),
(0, 0, 1, 0, 0),
(0, 0, 1, 0, 1),
(0, 0, 1, 1, 0),
(0, 0, 1, 1, 1),
(0, 1, 0, 0, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 1, 0),
(0, 1, 0, 1, 1),
(0, 1, 1, 0, 0),
(0, 1, 1, 0, 1),
(0, 1, 1, 1, 0),
(1, 0, 0, 0, 0),
(1, 0, 0, 0, 1),
(1, 0, 0, 1, 0),
(1, 0, 0, 1, 1),
(1, 0, 1, 0, 0),
(1, 0, 1, 0, 1),
(1, 0, 1, 1, 0),
(1, 1, 0, 0, 0),
(1, 1, 0, 0, 1),
(1, 1, 0, 1, 0),
(1, 1, 1, 0, 0)}


That said, this way you first have to create a potentially huge list and then reduce it. You can avoid storing repetitions as follows:

sage: def my_orbits(V):
....:     S = set()
....:     for v in V:
....:         for p in permutations(v):
....:     return S

sage: my_orbits(V)
{(0, 0, 0, 0, 1),
(0, 0, 0, 1, 0),
(0, 0, 0, 1, 1),
(0, 0, 1, 0, 0),
(0, 0, 1, 0, 1),
(0, 0, 1 ...
more

Thank you!

( 2016-06-02 16:13:15 +0200 )edit