Hot_Potato's blog

code for decomposing a permutation into a product of transpositions
By Hot_Potato, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are correct on the example part. But It has to be done in O(1)...no extra space can be used.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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.

      Code
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but the visited array itself is taking up space though!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +10 Vote: I do not like it

          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.

          → Reply