How can I generate all permutations of cyclic shifts of length k in a list of length n. Here shift is cyclic and right. Notice that:
if K==1 , there's no shift. Hence, no permutation of those 0 shifts.
if K==2 , this is equivalent to swapping the elements. Hence all n! permutations can be generated.
eg. if list is [1 4 2],K=2 (thus from 0 to N-K, loop)
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]
if K==3, things get interesting as some permutations are left out.
eg. if list=[1,3,4,2],K=3 ( thus from index 0 to 4-3,loop)
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.
Notice,that these permutations are half (12) of what should've been (24). To, implement this, algorithm, I am currently using backtracking. Here's what I have tried so far (in 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,[])
This produces the output
[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
This is exactly what I want, but a lot lot slower,since here the recursion depth exceeds for N>7. I hope, I have explained myself clearly. Anyone, with any optimizations?
The check
if P in stored_perms:
gets slower and slower as stored_perms grows, because it requires comparing P with the elements of stored_perms one at a time, until either a copy is found or the end of the list is encountered. Since every permutation will be added to stored_perms once, the number of comparisons with P is at least quadratic in the number of permutations found, which will generally be either all the possible permutations or half of them, depending on whether k is even or odd (assuming 1 < k < N).
It's a lot more efficient to use a set. Python's set is based on a hash-table, so the membership check is usually O(1) rather than O(N). However, there are a couple of limitations:
The elements added to the set need to be hashable, and Python lists are not hashable. Fortunately, tuples are hashable, so a small change fixes the issue.
Iterating over a set is unpredictable. In particular, you cannot reliably modify the set while you are iterating over it.
In addition to changing P to a tuple and stored_perms to a set, it's worthwhile considering search based on a workqueue instead of a recursive search. I don't know if it will be any faster, but it avoids any issues with recursion depth.
Putting all that together, I threw the following together:
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)