Given a list of strings lst and a list of integers p, reorder lst so that every lst[i] gets placed to p[i]. Example 1 Input
lst = ["a", "b", "c", "d"] p = [3, 0, 1, 2] Output
["b", "c", "d", "a"] Explanation
a goes to index 3 b goes to index 0 c goes to index 1 d goes to index 2
I am trying to solve this by decomposing permutation p into a product of transposition(swaps) and then use those swaps to reorder lst.. can anyone give me the code for decomposing a permutation into a product of transpositions? Note it has to be done in O(1) space..otherwise it is trivial
What exactly are you trying to do? You should give an example to explain the process / outcome you are looking for.
Let's say the list of strings, $$$ lst = \{a, b, c, d\}$$$, and the permutation $$$p = \{1, 4, 2, 3 \}$$$. Then you want the final order as $$$\{a, c, d, b \}$$$ ?
If yes, what is the big problem here, you simply need to make a new list and do, $$$ \text{nlst}[p[i]] = lst[i]$$$ for all $$$i$$$.
It's easy to see, because what you wrote
reorder so that every lst[i] gets placed to p[i], simply means for a string previously at index $$$i$$$, you want it to be at index $$$p[i]$$$ in the new list.You are correct on the example part. But It has to be done in O(1)...no extra space can be used.
If you want to use only $$$O(1)$$$ extra space, just keep a temporary variable and decompose the permutation in cycles.
Since you wanted to know how to decompose the permutation, it is quite simple, simply start at any index $$$i$$$ then go to $$$p[i]$$$, then to $$$p[p[i]]$$$ and so on, until you reach $$$i$$$ again. And use the extra variable to keep swapping the elements out from previous position and in to their new positions.
For example, consider the permutation $$$ p = \{1, 4, 5, 3, 6, 2\} $$$. I would break it into cycles as follows, start at $$$i = 1$$$, we get $$$ \{ 1 \} $$$. Then, start at $$$i = 2$$$, we get $$$ \{ 2 (i), 4 (p[i]) , 3 (p^2[i]), 5 (p^3[i]), 6 (p^4[i]) \} $$$
Note: $$$p^5[i]$$$ is $$$2$$$, so the cycle ends, and all indices are visited, so you have a decomposition.
This code assumes, that the array $$$p$$$ is stored with $$$0$$$-based indexing.
but the visited array itself is taking up space though!
Well, there is another trick which you can use, encode the "visited" status of an index in the permutation array by changing the $$$p[i]$$$ value to $$$-p[i]$$$. And at each place where you use $$$p[i]$$$, use $$$abs(p[i])$$$ instead.
Although, these things of restricting space are only useful in coding interviews. You would hardly face this kind of issue in competitive coding.