Thanks a lot for all the effort! This book is super awesome, but this particular problem is giving me a hard time
The python solution (http://elementsofprogramminginterviews.com/solutions/python/permutation_array1.py)
to permute the elements fails for the following testcase.
arr = [‘a’,‘b’,‘c’,‘d’]
p = [3,0,1,2] - Basically cyclically shifted right by 1.
The expected answer should have been - [‘d’,‘a’,‘b’,‘c’]
The code gives out - [‘b’, ‘c’, ‘d’, ‘a’]
Are there issues with the code?
Copying code for ease of debug :
def apply_permutation(perm, A):
for i in range(len(A)):
# Check if the element at index i has not been moved by checking if
# perm[i] is nonnegative.
next = i
while perm[next] >= 0:
A[i], A[perm[next]] = A[perm[next]], A[i]
temp = perm[next]
# Subtracts len(perm) from an entry in perm to make it negative,
# which indicates the corresponding move has been performed.
perm[next] -= len(perm)
next = temp
# Restore perm.
perm[:] = [a + len(perm) for a in perm]