Generate all possible permutation functions

Question

I am interested in finding the permutations p:S->S within a set S={1, 2, ..., n}. In particular, all the functions that either permute i and j: p(i)=j and p(j)=i; or leave them unchanged p(i)=i or p(j)=j.

For instance, if S={1,2,3}, I should get something like:

p0 = [(1), (2), (3)] # p(1)=1, p(2)=2, p(3)=3
p1 = [(1,2), (3)] # p(1)=2, p(2)=1, p(3)=3
p2 = [(1,3), (2)]
p3 = [(2,3), (1)]

If S={1, 2, 3, 4}:

p0 = [(1), (2), (3), (4)]
p1 = [(1,2), (3,4)]
p2 = [(1,2), (3), (4)]  # p(1)=2, p(2)=1, p(3)=3, p(4)=4
p3 = [(1,3), (2,4)]
p4 = [(1,3), (2), (4)]
p5 = [(1,4), (2,3)]
p6 = [(1,4), (2), (3)]
p7 = [(1), (3), (2,4)] 
p8 = [(1), (4), (2,3)]
p9 = [(1), (2), (3,4)]

Thanks.

What have you tried? You're clearly aware of `itertools`, it's not hard to use it for your building blocks once you're aware of it. — ShadowRanger, Nov 30 '16 at 03:27
I don't think there should so many downvotes, it's not about *arbitrary* permutations but rather a special subset of them. A efficient implementation is slightly tricky. — Kh40tiK, Nov 30 '16 at 03:31
@Kh40tiK: Asking for help without even making an attempt is not really in the spirit of SO. — ShadowRanger, Nov 30 '16 at 03:33
I realized that it requires an algorithm. I am interested in a more compact way of solving it with simple itertools. — rmas, Nov 30 '16 at 03:39
so you want all the [partition](https://en.wikipedia.org/wiki/Partition_of_a_set)? — Copperfield, Nov 30 '16 at 03:45
This almost answers your question: http://stackoverflow.com/a/5360442/4996248 Apply this answer to all sublists of even length (which can be generated by `itertools.combinations`) — John Coleman, Nov 30 '16 at 03:50
@Copperfield: Not all of them. I am only interested in i-j or i-i mappings. In [example 5](https://en.wikipedia.org/wiki/Partition_of_a_set#Examples), {{1, 2, 3}} shouldn't be included. — rmas, Nov 30 '16 at 03:50
this looks like what you want: http://stackoverflow.com/q/18353280/5644961 — Copperfield, Nov 30 '16 at 04:12
What are i and j? You say you want "all the functions that either permute i and j ... or leave them unchanged", but i and j come out of nowhere. Your example output looks like you're looking for all permutations of S whose cycle decomposition includes no cycles of length greater than two. Is that what you're looking for? — user2357112, Nov 30 '16 at 04:41
(Equivalently, all permutations of order at most 2, or all permutations that are their own inverses.) — user2357112, Nov 30 '16 at 04:43

AChampion · Answer 1 · 2016-11-30T05:30:14.790

Not sure how to do this in a constructive way but it's fairly simple to construct all permutations and filter out those that don't meet the criteria. No comments on the efficiency of this:

>>> data = 'abcd'
>>> [[data[i] for i in n] for n in it.permutations(range(len(data))) 
...                       if all(n[n[i]] == i for i in n)]
[['a', 'b', 'c', 'd'],
 ['a', 'b', 'd', 'c'],
 ['a', 'c', 'b', 'd'],
 ['a', 'd', 'c', 'b'],
 ['b', 'a', 'c', 'd'],
 ['b', 'a', 'd', 'c'],
 ['c', 'b', 'a', 'd'],
 ['c', 'd', 'a', 'b'],
 ['d', 'b', 'c', 'a'],
 ['d', 'c', 'b', 'a']]

Kh40tiK · Accepted Answer · 2016-11-30T06:36:16.763

Assuming the goal is to find permutation involving only binary swaps.

from itertools import combinations

def opairs(li):
    if not li:
        yield []
        return
    li_cpy = li.copy()
    for h in range(1,len(li)):
        li_cpy = li[1:]
        del(li_cpy[h-1])
        for subli in opairs(li_cpy):
            yield [(li[0], li[h])] + subli

def swaps(n):
    assert n%2==0
    yield list(map(lambda _: (_,), range(n)))
    for subsize in range(1, n//2+1):
        for head in combinations(range(n), subsize*2):
            tail = []
            ihead = iter(head)
            ihead_next = next(ihead)
            for i in range(n):
                if i==ihead_next:
                    try:
                        ihead_next = next(ihead)
                    except: continue
                else:
                    tail.append((i,))
            for phead in opairs(list(head)):
                yield phead+tail

for p in swaps(4): print(p)

Outputs:

[(0,), (1,), (2,), (3,)]
[(0, 1), (2,), (3,)]
[(0, 2), (1,), (3,)]
[(0, 3), (1,), (2,)]
[(1, 2), (0,), (3,)]
[(1, 3), (0,), (2,)]
[(2, 3), (0,), (1,)]
[(0, 1), (2, 3)]
[(0, 2), (1, 3)]
[(0, 3), (1, 2)]

Generate all possible permutation functions

2 Answers2