Algorithm to apply permutation in constant memory space

by

There is a trivial O(n^2) algorithm, but you can do this in O(n). E.g.:

A = [a, b, c, d, e]

P = [4, 3, 2, 0, 1]

We can swap each element in A with the right element required by P, after each swap, there will be one more element in the right position, and do this in a circular fashion for each of the positions (swap elements pointed with ^s):

[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4
 ^           ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1
    ^        ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3
    ^     ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step

After one circle, we find the next element in the array that does not stay in the right position, and do this again. So in the end you will get the result you want, and since each position is touched a constant time (for each position, at most one operation (swap) is performed), it is O(n) time.

You can stored the information of which one is in its right place by:

  1. set the corresponding entry in P to -1, which is unrecoverable: after the operations above, P will become [-1, -1, 2, -1, -1], which denotes that only the second one might be not in the right position, and a further step will make sure it is in the right position and terminates the algorithm;

  2. set the corresponding entry in P to -n - 1: P becomes [-5, -4, 2, -1, -2], which can be recovered in O(n) trivially.

More Related Contents:

  1. How to sort in-place using the merge sort algorithm?
  2. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  3. maximize the top element of the stack after performing exactly K operations
  4. Algorithm for all subsets of Array
  5. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  6. Finding three elements in an array whose sum is closest to a given number
  7. How to find the kth smallest element in the union of two sorted arrays?
  8. Can min/max of moving window achieve in O(N)?
  9. Weighted random selection from array
  10. Print two-dimensional array in spiral order
  11. Find the Smallest Integer Not in a List
  12. How to find a duplicate element in an array of shuffled consecutive integers?
  13. Find the majority element in array
  14. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  15. Binary Search algorithm implementations
  16. Algorithm to determine if array contains n…n+m?
  17. Find the 2nd largest element in an array with minimum number of comparisons
  18. Find all subsets of length k in an array
  19. How can I generate all permutations of an array in Perl?
  20. Print all permutation in lexicographic order
  21. Maximum single-sell profit
  22. Finding all permutations of array elements as concatenated strings
  23. How to find max. and min. in array using minimum comparisons?
  24. Regarding in-place merge in an array
  25. Interview question: three arrays and O(N*N)
  26. How to find repeating sequence of characters in a given array?
  27. Maximum sum of non consecutive elements
  28. Finding kth smallest number from n sorted arrays
  29. calculating the number of “inversions” in a permutation
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment