在長度爲N的列表中生成長度爲K的循環移位的所有置換

Question

如何在長度爲n的列表中生成長度爲k的循環移位的所有置換。這裏的轉變是循環和正確的。請注意：

如果K == 1，則不會發生移位。因此，這些0轉變沒有排列。
如果K == 2，這相當於交換元素。因此所有n！可以生成排列。

例如。如果列表是[1 4 2]，K = 2（因而從0到N-K，循環）

P1: [1,4,2] #Original list. No shift. 
P2: [4,1,2] #Shift from 0 of [1,4,2] 
P3: [4,2,1] #Shift from 1 of [4,1,2] as 0 gives P1 
P4: [2,4,1] #Shift from 0 of [4,2,1] 
P5: [2,1,4] #Shift from 1 of [1,4,2] as 0 of P4=P3 
P6: [1,2,4] #Shift from 0 of [2,1,4] 

如果滿足K == 3，事情就變得有趣，因爲一些置換被排斥在外。

例如。如果列表= [1,3,4,2]，K = 3（因此從索引0到4-3，環）

P1 : [1,3,4,2] #Original list. No shift. 
P2 : [4,1,3,2] #Shift from 0th of [1,3,4,2] 
P3 : [3,4,1,2] #Shift from 0th of [4,1,3,2] 
P4 : [3,2,4,1] #Shift from 1th of [3,4,1,2] as 0th gives P1 
P5 : [4,3,2,1] #Shift from 0th of [3,2,4,1] 
P6 : [2,4,3,1] #Shift from 0th of [4,3,2,1] 
P7 : [2,1,4,3] #Shift from 1th of [2,4,3,1] as 0th gives P3 
P8 : [4,2,1,3] #Shift from 0th of [2,1,4,3] 
P9 : [1,4,2,3] #Shift from 0th of [4,2,1,3] 
P10: [2,3,1,4] #Shift from 1th of [2,1,4,3] as 0 from P9=P7,1 from P9=P1,1 from P8=P5 
P11: [1,2,3,4] #Shift from 0th of [2,3,1,4] 
P12: [3,1,2,4] #Shift from 0th of [1,2,3,4] 

#Now,all have been generated, as moving further will lead to previously found values. 

注意的是，這些排列是一半（12）的什麼應該是（24）。 爲了實現這個算法，我正在使用回溯。以下是我已經（在Python）

def get_possible_cyclic(P,N,K,stored_perms): #P is the original list 
    from collections import deque 

    if P in stored_perms: 
     return #Backtracking to the previous 

    stored_perms.append(P) 

    for start in xrange(N-K+1): 
     """ 
     Shifts cannot wrap around. Eg. 1,2,3,4 ,K=3 
     Recur for (1,2,3),4 or 1,(2,3,4) where() denotes the cycle 
     """ 
     l0=P[:start]     #Get all elements that are before cycle ranges 
     l1=deque(P[start:K+start])  #Get the elements we want in cycle 
     l1.rotate()      #Form their cycle 
     l2=P[K+start:]     #Get all elements after cycle ranges 

     l=l0+list(l1)+l2    #Form the required list 
     get_possible_cyclic(l,N,K,stored_perms) 

    for index,i in enumerate(stored_perms):  
     print i,index+1 

get_possible_cyclic([1,3,4,2],4,3,[]) 
get_possible_cyclic([1,4,2],3,2,[]) 

到目前爲止已經試過這將產生輸出

[1, 3, 4, 2] 1 
[4, 1, 3, 2] 2 
[3, 4, 1, 2] 3 
[3, 2, 4, 1] 4 
[4, 3, 2, 1] 5 
[2, 4, 3, 1] 6 
[2, 1, 4, 3] 7 
[4, 2, 1, 3] 8 
[1, 4, 2, 3] 9 
[2, 3, 1, 4] 10 
[1, 2, 3, 4] 11 
[3, 1 ,2, 4] 12 

[1, 4, 2] 1 
[4, 1, 2] 2 
[4, 2, 1] 3 
[2, 4, 1] 4 
[2, 1, 4] 5 
[1, 2, 4] 6 

這正是我想要的，但很多慢了很多，因爲這裏遞歸深度超過N> 7。我希望，我已經清楚地解釋了自己。任何人，有任何優化？

Answer 1

支票

if P in stored_perms: 

變得慢如stored_perms增長，因爲它需要在一個時間比較P與stored_perms一個元素，直到一個副本被發現或列表的末尾遇到。由於每個置換將被添加到stored_perms一次，所以與P比較的次數在所找到的置換數量上至少是二次的，這通常將是所有可能的置換或其中的一半，這取決於k是偶數還是奇數假設1 < k < N）。使用set更有效率。 Python的集合基於哈希表，所以成員資格檢查通常是O（1）而不是O（N）。然而，也有一些限制：

1. 添加到集合中的元素必須是hashable，和Python列表不是可哈希。幸運的是，元組是可散列的，所以一個小的改變就可以解決這個問題。

2. 對集合進行迭代是不可預知的。特別是，當您迭代它時，您無法可靠地修改該設置。

除了更改P到一個數組和stored_perms一組，它是一個基於工作隊列，而不是一個遞歸搜索值得考慮的搜索。我不知道它是否會更快，但它可以避免任何遞歸深度問題。

把所有在一起，我扔在一起以下幾點：

def get_cyclics(p, k): 
    found = set()  # set of tuples we have seen so far 
    todo = [tuple(p)] # list of tuples we still need to explore 
    n = len(p) 
    while todo: 
    x = todo.pop() 
    for i in range(n - k + 1): 
     perm = (x[:i]     # Prefix 
      + x[i+1:i+k] + x[i:i+1] # Rotated middle 
      + x[i+k:]     # Suffix 
      ) 
     if perm not in found: 
     found.add(perm) 
     todo.append(perm) 
    for x in found: 
    print(x)