如何在長度爲n的列表中生成長度爲k的循環移位的所有置換。這裏的轉變是循環和正確的。請注意:在長度爲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。我希望,我已經清楚地解釋了自己。任何人,有任何優化?
開始嘗試隨整數:1,2,然後1,2,3,最後1,2,3,4 - 檢查由正確答案手,然後在結果中查找模式。 – Paddy3118
我收集了你正在嘗試從正在進行的CodeChef比賽中解決問題[PERSHFTS](https://www.codechef.com/OCT15/problems/PERSHFTS)。枚舉不會幫助你。 –
哈哈,是的,我知道。這是一個排列簡單的奇偶校驗,並打印其詞典索引/ 2。我只是熱衷於改進我原來的方法,因爲我總是從粗暴開始,並在我繼續時進行優化。謝謝,雖然你的提示。 –