Permute the elements of an array - testcase not working on book solution

#1

Hello,

Thanks a lot for all the effort! This book is super awesome, but this particular problem is giving me a hard time :smile:

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]
return A

0 Likes
#2

All,

Upon reading the problem I realized I misunderstood the problem! Each element in the perm indicates the position of the ith element in the new permutation.

I misunderstood it as the ith element in the new permutation should be arr[perm[i]].

Sorry for the confusion! But glad I finally got it:) Because of my misunderstanding spent nearly 2 hours just to understand what’s wrong!

0 Likes
#3

Hi @girishpai,

Thanks for your question, and feel free to let us know if you have any question in the future.

0 Likes