我怎样才能在长度n的列表中生成长度k的循环移位的所有置换。这里的移位是循环的和右的注意：
如果k==1，就没有移位。因此，这0个位移没有排列。
如果k==2，这相当于交换元素。因此所有的N！可以生成置换。
例如，如果列表是[14 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，事情会变得有趣，因为一些置换被忽略了。
例如，如果list=[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.
注意，这些排列是应该是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。我希望，我已经解释清楚了有人，有什么优化吗？
最佳答案
支票
if P in stored_perms:
随着
stored_perms的增长越来越慢，因为它需要一次将P与stored_perms的元素进行比较，直到找到副本或遇到列表的结尾。由于每一个置换将被添加到stored_perms一次，与P的比较的次数在所发现的置换的次数中至少是二次的，这通常是所有可能的置换或其中的一半，这取决于k是偶数还是奇数（假设1使用set会更有效。python的集合基于散列表，因此成员资格检查通常是o（1）而不是o（n）。但是，有两个限制：添加到集合的元素需要hashable，并且python列表不可哈希。幸运的是，元组是散列的，所以一个小的改变就解决了这个问题。
在集合上迭代是不可预测的尤其是，在迭代集合时，不能可靠地修改它。
除了将P改为元组并将存储的_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)
关于python - 有效地生成长度为N的列表中长度为K的循环移位的所有置换，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32953585/