Ask Your Question

Revision history [back]

If you want the whole group of permutations act on your set, i would suggest to use the itertools Python module which is pretty optimized and can be 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),
...

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, 1, 0, 0, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 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, 1, 0),
 (0, 1, 0, 0, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)}

If you want the whole group of permutations act on your set, 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 can be 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),
...

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, 1, 0, 0, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 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, 1, 0),
 (0, 1, 0, 0, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)}

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

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, 1, 0, 0, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 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, 1, 0), (0, 1, 0, 0, 0), (0, 1, 0, 0, 1), (0, 1, 0, 1, 0), (0, 1, 1, 0, 0), (1, 0, 0, 0, 0), (1, 0, 0, 0, 1), (1, 0, 0, 1, 0), (1, 0, 1, 0, 0), (1, 1, 0, 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)}

One last thing: i am not sure about the exact specification of your input. If the vectors are 0-1 vectors, then of course the permutations are only combinations, hence only depend on the number of 1's (which you can get with the L1 norm, or the sum of the tuple). Here are some hints:

sage: v = (0,1,1,0,0)
sage: sum(v)
2
sage: len(v)
5

You can get the list of possible spots fot the 1 value as follows:

sage: list(combinations(range(5), 2))
[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

Also, you can use IntegerListLex (see IntegerListLex? for the doc of all possibilities it provides) to get, all non-negative integer sequences with max_part=1 (so that you have only 0-1 sequences), whose sum (hence the number of 1) is n=3, whose length is 5:

sage: list(IntegerListsLex(n=3, max_part=1, length=5))
[[1, 1, 1, 0, 0],
 [1, 1, 0, 1, 0],
 [1, 1, 0, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 1, 1, 0, 1],
 [0, 1, 0, 1, 1],
 [0, 0, 1, 1, 1]]

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

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, 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)}

{(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)}

One last thing: i am not sure about the exact specification of your input. If the vectors are 0-1 vectors, then of course the permutations are only combinations, hence only depend on the number of 1's (which you can get with the L1 norm, or the sum of the tuple). Here are some hints:

sage: v = (0,1,1,0,0)
sage: sum(v)
2
sage: len(v)
5

You can get the list of possible spots fot the 1 value as follows:

sage: list(combinations(range(5), 2))
[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

Also, you can use IntegerListLex (see IntegerListLex? for the doc of all possibilities it provides) to get, all non-negative integer sequences with max_part=1 (so that you have only 0-1 sequences), whose sum (hence the number of 1) is n=3, whose length is 5:

sage: list(IntegerListsLex(n=3, max_part=1, length=5))
[[1, 1, 1, 0, 0],
 [1, 1, 0, 1, 0],
 [1, 1, 0, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 1, 1, 0, 1],
 [0, 1, 0, 1, 1],
 [0, 0, 1, 1, 1]]

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, 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)}

One last thing: i am not sure about the exact specification of your input. If the vectors are 0-1 vectors, then of course the permutations are only combinations, hence only depend on the number of 1's (which you can get with the L1 norm, or the sum of the tuple). Here are some hints:

sage: v = (0,1,1,0,0)
sage: sum(v)
2
sage: len(v)
5

You can get the list of possible spots fot the 1 value as follows:

sage: list(combinations(range(5), 2))
[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

Also, you can use IntegerListLex (see IntegerListLex? for the doc of all possibilities it provides) to get, all non-negative integer sequences with max_part=1 (so that you have only 0-1 sequences), whose sum (hence the number of 1) is n=3, whose length is 5:

sage: list(IntegerListsLex(n=3, max_part=1, length=5))
[[1, 1, 1, 0, 0],
 [1, 1, 0, 1, 0],
 [1, 1, 0, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 0, 1, 0, 1],
 [1, 0, 0, 1, 1],
 [0, 1, 1, 1, 0],
 [0, 1, 1, 0, 1],
 [0, 1, 0, 1, 1],
 [0, 0, 1, 1, 1]]