Given an array A = [a1, a2, ..., an] and another array B, where B is some permutation of the numbers 1, 2, ... n, how can I order the elements of A according to the permutation B in-place (so you cannot make an extra array)?
For example, if A = [27, 15, 11, 19] and B = [3, 2, 4, 1], then we would have to modify A to get [19, 15, 27, 1].
This problem seems really easy at first, but I thought it was quite difficult with the memory constraint. I wasn't able to solve this problem, but I was wondering whether someone else would be able to show me how to solve it.
i think we can sort array B and apply same operations on A as applied on B while sorting. resulting array A might give you result!!
You need ~4 temporary variables and O(n) time complexity. Read about https://en.wikipedia.org/wiki/Permutation#Cycle_notation
I am sort of confused. I have read that page, and I still cannot figure out the problem. I am pretty sure it will be some sort of composition of A and B, but I can't quite figure it out.
https://blog.merovius.de/2014/08/12/applying-permutation-in-constant.html
I think qwertyy123321 was onto something, but they didn't fully complete the solution.
The main idea is to sort $$$B$$$ and mirror every operation on $$$A$$$ that we do on $$$B$$$, as itachi0012 said.
One easy way to do this is to use something like
std::sort
and define our comparator to be based on the elements of $$$B$$$. This is equivalent to assigning pairs of $$$(B_i, A_i)$$$ and callingstd::sort
on that, which will clearly work. This is $$$O(nlogn)$$$ with $$$O(1)$$$ space because the three algorithms (quicksort, heapsort, and insertion sort) ofstd::sort
, which is introsort under the hood, are all in-place sorting algorithms and use $$$O(1)$$$ memory.Another way is to factor in the link that bruno.iljazovic posted, which shows that a permutation can be decomposed into a bunch of cycles. A cycle for a permutation $$$P$$$ is essentially starting from any $$$i$$$ and moving to the index $$$P_i$$$ until you eventually return to $$$i$$$, which will happen. We'll treat each cycle separately, and use the following algorithm ($$$1$$$-indexed):
This will sort any cycle going through $$$i$$$, because it will essentially traverse the cycle starting at the position right after $$$i$$$ and correct each element one by one until $$$i$$$ is corrected, which will be the last element to be corrected (because $$$i$$$ is the last element in the cycle, according to where we start each time). Since each element gets at most $$$1$$$ correction and we look at each index $$$1$$$ time, the overall complexity is $$$O(n)$$$, with no additional space.
I also quickly wrote a bash to try to verify this solution by checking if it sorted every permutation of $$$0..9$$$ ($$$0$$$-indexed), and it was successful.