すべての可能な順列関数を生成する

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}、Iのようなものを取得する必要：

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

バイナリスワップのみを含む順列を見つけることを目標とすると仮定します。

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

Answer 2

建設的な方法でこれを行う方法がわかりませんが、すべての順列を構築し、条件を満たすものを除外するのはかなり簡単です。この効率のコメントはありません。

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