모든 가능한 순열 함수 생성

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

목표는 바이너리 스왑 만 포함하는 순열을 찾는 것이라고 가정합니다.

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