Блог пользователя Hot_Potato

Автор Hot_Potato, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      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
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        but the visited array itself is taking up space though!

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

          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.