Problem 5.10 - Permute the elements of an array

#1

My solution to this problem is strangely simple, and it did pass all the test cases on EPI judge. In fact it runs twice as fast as the solution given in the github repository.

I don’t understand why the textbook contains such cumbersome solution.

My solution is as follows.

def apply_permutation(P, A):
    for i in range(len(A)):
        while P[i] != i:
            A[i], A[P[i]] = A[P[i]], A[i]
            a = P[i]
            b = P[P[i]]
            P[i] = b
            P[a] = a

In each iteration of the for loop, I first exchange A[i] with A[P[i]] which moves A[i] in its correct location. I also exchange P[i] and P[P[i]] so that P[P[i]] becomes equal to P[i]. Now, we might have an incorrect element at A[i]. I repeat the above steps until I get the correct element in position A[i]. Since each swap places one element in correct position, the time complexity is O(n).

I don’t understand why this much simpler solution is not discussed in the book. Am I missing something here?

Here is the runtime of my program -

PS C:\Users\amogh\stuff\algo_ds.py\epi_judge> python 
.\epi_judge_python\apply_permutation.py 
Test PASSED (101/101) [  50 ms]
Average running time:  551 us 
Median running time:    36 us
*** You've passed ALL tests. Congratulations! ***

Here is the runtime of the solution provided in the github repository -

PS C:\Users\amogh\stuff\algo_ds.py\epi_judge> python 
.\epi_judge_python\apply_permutation.py
Test PASSED (101/101) [  80 ms]
Average running time:  900 us
Median running time:    76 us
*** You've passed ALL tests. Congratulations! ***
0 Likes
#2

Hi @amogh09,

Many thanks for this genius solution, and I think it definitely is a great solution that simulates the process of permutation. One thing I think the drawback of this approach is that this approach will totally modify the perm array without being able to restore it.

Overall, I really like your idea of this solution, and please keep us posted of this!

0 Likes
#3

Hi @amogh09,

BTW, I tried your idea and implement as follows:

     def apply_permutation(perm, A):
         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]]

Thanks again for this idea.

0 Likes
#4

Hi @tsunghsienlee, thank you so much for your response. I love the succinct snippet you provided which is the trademark of your book. :slight_smile:

By the way, I realized that the concept of cyclic permutations that you introduced in the solution to problem 5.10 is being used in problem 24.6 (Rotate an array). I will now understand the solutions you presented.

Thank you once again. :slight_smile:

0 Likes
#5

Hi, do you have any idea for the first variant (no additional memory and no change in P)?

0 Likes