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!

@Martijn Pieters and unutbu: Thank you, but I need to use reverse function (it is simplified here). Actually instead of reverse must be any function, which modifies element. Element could be a list. — pro100
– pro100, Commented Feb 19, 2014 at 20:51

unutbu · Accepted Answer · 2014-02-19 21:36:46Z

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)]

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)]

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)]

Martijn Pieters · Accepted Answer · 2014-02-19 20:25:24Z

0

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)

answered Feb 19, 2014 at 20:25

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

1 Comment

simonzack Over a year ago

This includes [1, -1]

Collectives™ on Stack Overflow

Permutations with modifications in python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related