 # 05.10 Permute The Elements Of An Array (Solutions in old/new versions do not work)

#1

Hi, all.

I am using Python 3.7.
I found out the solutions in the old book and new book do not work.
(sorry, I could not figure out how to make indentations… Can some one let me know how to do this?)

def apply_permutation_med(perm:list, A:list):
for i in range(len(A)):
while perm[i] != i:
A[perm[i]] , A[i] = A[i], A[perm[i]]
perm[perm[i]], perm[i] = perm[i],perm[perm[i]]

A1 = [‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’]
perm1 = [1,4,5,0,2,6,3]
print(apply_permutation_med(perm = perm1, A = A1))
print(A1)

A2 = [‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’]
perm2 = [1,5,4,0,2,6,3]
print(apply_permutation_med(perm = perm2, A = A2))
print(A2)

A3 = [‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’]
perm3 = [3, 0, 1, 6, 5, 4, 2]
print(apply_permutation_med(perm = perm3, A = A3))
print(A3)

## Old version solution test:

def apply_permutation(perm:list, A: list )-> list:
for i in range(len(A)-1):
# print(’---------------------------’)
next = i
while perm[next] >= 0:
#
# print(‘i:’,i)
# print(‘perm[next]’, perm[next])
A[i], A[perm[next]] = A[perm[next]], A[i]
temp = perm[next]
perm[next] -= len(perm) # make the perm[next] negative, marking it as “DONE”
next= temp
# print(A)
# restore perm
perm[:] = [a+len(perm) for a in perm]

A1 = [‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’]
perm1 = [1,5,4,0,2,6,3] # non-cyclic gives an error to the solution
print(apply_permutation(perm = perm1, A = A1))
print(A1)

It is strange that the solution passed all the test cases in EPI judge.

0 Likes