Given two arrays which have same values but in different order, we need to make second array same as first array using minimum number of swaps.
Examples:
Input : arrA[] = {3, 6, 4, 8},
arrB[] = {4, 6, 8, 3}
Output : 2
we can make arrB to same as arrA in 2 swaps
which are shown below,
swap 4 with 8, arrB = {8, 6, 4, 3}
swap 8 with 3, arrB = {3, 6, 4, 8}
This problem can be solved by modifying the array B. We save the index of array A elements in array B i.e. if ith element of array A is at jth position in array B, then we will make arrB[i] = j
For above given example, modified array B will be, arrB = {3, 1, 0, 2}. This modified array represents distribution of array A element in array B and our goal is to sort this modified array in minimum number of swaps because after sorting only array B element will be aligned with array A elements.
Now count of minimum swaps for sorting an array can be found by visualizing the problem as a graph, this problem is already explained in previous article.
So we count these swaps in modified array and that will be our final answer.
Please see below code for better understanding.
// C++ program to make an array same to another
// using minimum number of swap
#include <bits/stdc++.h>
using namespace std;
// Function returns the minimum number of swaps
// required to sort the array
// This method is taken from below post
// http://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
int minSwapsToSort(int arr[], int n)
{
// Create an array of pairs where first
// element is array element and second element
// is position of first element
pair<int, int> arrPos[n];
for (int i = 0; i < n; i++)
{
arrPos[i].first = arr[i];
arrPos[i].second = i;
}
// Sort the array by array element values to
// get right position of every element as second
// element of pair.
sort(arrPos, arrPos + n);
// To keep track of visited elements. Initialize
// all elements as not visited or false.
vector<bool> vis(n, false);
// Initialize result
int ans = 0;
// Traverse array elements
for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrPos[i].second == i)
continue;
// find out the number of node in
// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = 1;
// move to next node
j = arrPos[j].second;
cycle_size++;
}
// Update answer by adding current cycle.
ans += (cycle_size - 1);
}
// Return result
return ans;
}
// method returns minimum number of swap to make
// array B same as array A
int minSwapToMakeArraySame(int a[], int b[], int n)
{
// map to store position of elements in array B
// we basically store element to index mapping.
map<int, int> mp;
for (int i = 0; i < n; i++)
mp[b[i]] = i;
// now we're storing position of array A elements
// in array B.
for (int i = 0; i < n; i++)
b[i] = mp[a[i]];
/* We can uncomment this section to print modified
b array
for (int i = 0; i < N; i++)
cout << b[i] << " ";
cout << endl; */
// returing minimum swap for sorting in modified
// array B as final answer
return minSwapsToSort(b, n);
}
// Driver code to test above methods
int main()
{
int a[] = {3, 6, 4, 8};
int b[] = {4, 6, 8, 3};
int n = sizeof(a) / sizeof(int);
cout << minSwapToMakeArraySame(a, b, n);
return 0;
}
Output:
2
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.