Ask Your Question
1

Group Acting on a Set

asked 2016-06-01 15:42:34 -0500

JEA gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2016-06-02 03:32:05 -0500

tmonteil gravatar image

updated 2016-06-02 04:37:38 -0500

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):
....:             S.add(p)
....:     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)
edit flag offensive delete link more

Comments

Thank you!

JEA gravatar imageJEA ( 2016-06-02 09:13:15 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-06-01 15:42:34 -0500

Seen: 52 times

Last updated: Jun 02 '16