3

I have two arrays A and B of the same length.

A and B contain the same elements but in different order.

I need to make A match B by only swapping any two elements within A. I also need to do this in the minimum number of swaps possible. The array(s) can contain duplicate elements.

For example if

A = { 3, 8, 5, 8 }

B = { 8, 8, 3, 5 }

The minimum needed swaps is 2 and the sequence would be

swap(0, 2)
swap(0, 3)

I know how to find how many swaps are needed from sources like here, or here but I cannot find any information on generating the sequence of swaps needed to make A match B. I believe the solution involves directed graphs and cycles but I can't quite figure out a working algorithm that is less than O(n^2) time.

Hatefiend
  • 3,416
  • 6
  • 33
  • 74
  • 1
    You can modify [algorithm](https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/): for each cycle store indexes and generate swaps for them. Cycle: 0->2->4->6->0 gives swaps: (0,2), (2,4), (4,6) – Kozyr Nov 07 '18 at 09:15
  • 1
    Possible duplicate of [Finding the minimum number of swaps to convert one string to another, where the strings may have repeated characters](https://stackoverflow.com/questions/18292202/finding-the-minimum-number-of-swaps-to-convert-one-string-to-another-where-the) – juvian Nov 07 '18 at 14:32

0 Answers0