Сгенерировать все возможные функции перестановок

Question

Меня интересует поиск перестановок p: S-> S в множестве S = {1, 2, ..., n}. В частности, все функции, которые либо переставляют 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']]