Permutations with modifications in python

Question

I am stuck on following problem: there is normal permutation function:

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

Here I get as expected

for pz in all_perms([1,2,3]):
    print(pz)

[1, 2, 3]
[2, 1, 3]
[2, 3, 1]
[1, 3, 2]
[3, 1, 2]
[3, 2, 1]

Then I have simple reverse function:

def reverse(rx):
    return -rx

How could look function perm_rev(iterable) resulting in permutation assuming each element has to be reversed? Answer for [1,2] would be like this:

for pz in perm_rev([1,2]):
    print(pz)

[1,2]
[2,1]
[-1,2]
[1,-2]
[-2,1]
[2,-1]
[-1,-2]
[-2,-1]

Thank you!

Answer 1

import itertools as IT
def perm_rev(iterable):
    for grp in IT.product(*[[x, -x] for x in iterable]): # 1
        for item in IT.permutations(grp):                # 2
            yield item

For example,

In [46]: list(perm_rev([1,2]))
Out[46]: [(1, 2), (2, 1), (1, -2), (-2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1)]

1. For each x in iterable, grp selects either x or -x. For example,

   In [53]: list(IT.product([-1,1], [-2,2])) 
   Out[53]: [(-1, -2), (-1, 2), (1, -2), (1, 2)]
   

2. Then for each grp, generate the permutions of grp.

---

Note also that your all_perms could be written in terms of itertools.permutations:

def all_perms(elements):
    return IT.permutations(elements)

The two are essentially the same (except for the order of the elements, and that IT.permutations returns an iterator instead of a list).

---

To generalize perm_rev to apply a function other than reverse, you could do this:

def reverse(x):
    return [x, -x]

def perm_rev(iterable, options):
    for grp in IT.product(*[options(x) for x in iterable]): 
        for item in IT.permutations(grp):                
            yield item

Then, call perm_rev like this:

In [58]: list(perm_rev([1,2], reverse))
Out[58]: [(1, 2), (2, 1), (1, -2), (-2, 1), (-1, 2), (2, -1), (-1, -2), (-2, -1)]

Answer 2

Add in reversals in a generator function, with a itertools.product() call:

def perm_rev(seq):
    for perm in permutations(seq):
        for prod in product(*((i, -i) for i in perm)):
            yield prod

Demo:

>>> for pz in perm_rev([1,2]):
...     print(pz)
... 
(1, 2)
(1, -2)
(-1, 2)
(-1, -2)
(2, 1)
(2, -1)
(-2, 1)
(-2, -1)