0

Let's say we have two arrays: Array a1 and Array a2.

'a1' and 'a2' are similar in a way such that both have the same size and same elements but elements don't appear in the same order.

What will be the most effective way of comparing both arrays and finding out the minimum number of swaps required to bring the array 'a1' in the same order as 'a2'?

For example:

int a1[5] = { 1, 2, 3, 4, 5};
int a2[5] = { 2, 3, 1, 5, 4};

Hence the minimum number of swaps required is: 3

In steps:

swap 1: a1[0] <-> a1[1]

swap 2: a1[1] <-> a1[2]

swap 3: a1[3] <-> a1[4]

So, finally a1 will contain { 2, 3, 1, 5, 4}

Jens Gustedt
  • 76,821
  • 6
  • 102
  • 177
Shubham Ranjan
  • 1
  • 2
  • Are the numbers the integers from 1 to n ? –  Jul 23 '17 at 10:31
  • 1
    there is known algorithm for this: [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance) . Although it is a little more general. I don't know if for your restrictions can be improved or if there is another one faster for your restrictions. – bolov Jul 23 '17 at 10:53
  • (Sorry, I think this should be a comment, but I don't have 50 reputations to make one) Unless I'm missing something, this has been asked before and you will likely find your answer here: https://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2 – szmate1618 Jul 23 '17 at 13:43

1 Answers1

0
int numofchanges = 0;
for(int i = 0; i < sizeOfArrays; i++)
{
    int arr3[] = arr1;
    for(int n = 0; n < sizeOfArrays; n++)
    {
         arr3[i] = arr1[n];
         if(arr3[i] == arr2[i])
         {
             int tmp = arr1[i];
             arr1[i] = arr1[n];
             arr1[n] = tmp;
             numofchanges++;
         }
    }
}

WARRNING this wont run is something like pseudo code

the variable numofchanges will hold the number of changes and arr1 now will be arr2

i hope this was helpful