生成所有可能的置换函数

Question

我有兴趣在集合 S={1, 2, ..., n} 中找到排列 p:S->S。特别是，所有置换 i 和 j 的函数：p(i)=j 和 p(j)=i；或保持不变 p(i)=i 或 p(j)=j.

例如，如果 S={1,2,3}，我应该得到如下内容：

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

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

谢谢。

Answer 1

不确定如何以建设性的方式执行此操作，但构造所有排列并过滤掉不符合条件的排列相当简单。对此效率无评论：

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

Answer 2

假设目标是找到仅涉及二进制交换的排列。

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)

输出：

[(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

python

list

set

combinatorics

itertools