wish_me's blog

Minimum number of swaps required for arranging pairs adjacent to each other
By wish_me, history, 7 years ago, In English

There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.

n<10^3 arr.size<10^3

Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

(Google Interview)

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

http://www.lmgtfy.com/?q=Minimum+swap+for+arranging+adacent+pair

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    your jokes are worth your rating

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

      That wasn't a joke... I was just telling him to first google the question and then only ask here.

      PS-> Your views tell a lot about your thinking about people below you(rating wise)... God bless you :-)

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

        Let's call a spade a spade. That wasn't a friendly advice to google the question. He is wise who says nothing when he has nothing to say.

        PS-> Your jokes tell a lot about your thinking about people below you(rating wise)... God bless you :-)

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

Up. I met this problem before and know linear reference solution but I can't prove it :(

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

    The solution which makes swaps along the cycles of permutation?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yep.

      Consider first two elements. If they are partners then skip them and move to the next two elements. Otherwise find a pair for any of these two elements (suppose the pair was among a[2k] and a[2k + 1]), make swap, now move to elements with indexes 2k and 2k + 1 and repeat step.

      → Reply