Generiere alle möglichen Permutationsfunktionen

Question

Ich interessiere mich für die Permutationen p: S-> S innerhalb einer Menge S = {1, 2, ..., n}. Insbesondere alle Funktionen, die entweder i und j vertauschen: p (i) = j und p (j) = i; oder lassen sie unverändert p (i) = i oder p (j) = j.

Zum Beispiel, wenn S = {1,2,3}, soll ich so etwas wie:

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

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

Danke.

Answer 1

Angenommen, das Ziel ist es, Permutation nur mit binären Swaps zu finden.

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) 

Ausgänge:

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

Nicht sicher, wie dies auf eine konstruktive Art und Weise zu tun ist, aber es ist ziemlich einfach, alle Permutationen zu konstruieren und diejenigen herauszufiltern, die die Kriterien nicht erfüllen. Keine Kommentare zu der Effizienz dieser:

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