## Tuesday, November 29, 2016

### Minimum swaps to make two arrays identical - GeeksforGeeks

Minimum swaps to make two arrays identical - GeeksforGeeks
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.

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.

`// 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);`
`}`
http://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
`    ``public` `static` `int` `minSwaps(``int``[] arr)`
`    ``{`
`        ``int` `n = arr.length;`

`        ``// Create two arrays and use as pairs where first`
`        ``// array is element and second array`
`        ``// is position of first element`
`        ``ArrayList <Pair <Integer, Integer> > arrpos =`
`                  ``new` `ArrayList <Pair <Integer, Integer> > ();`
`        ``for` `(``int` `i = ``0``; i < n; i++)`
`             ``arrpos.add(``new` `Pair <Integer, Integer> (arr[i], i));`

`        ``// Sort the array by array element values to`
`        ``// get right position of every element as the`
`        ``// elements of second array.`
`        ``arrpos.sort(``new` `Comparator<Pair<Integer, Integer>>()`
`        ``{`
`            ``@Override`
`            ``public` `int` `compare(Pair<Integer, Integer> o1,`
`                               ``Pair<Integer, Integer> o2)`
`            ``{`
`                ``if` `(o1.getValue() > o2.getValue())`
`                    ``return` `-``1``;`

`                ``// We can change this to make it then look at the`
`                ``// words alphabetical order`
`                ``else` `if` `(o1.getValue().equals(o2.getValue()))`
`                    ``return` `0``;`

`                ``else`
`                    ``return` `1``;`
`            ``}`
`        ``});`

`        ``// To keep track of visited elements. Initialize`
`        ``// all elements as not visited or false.`
`        ``Boolean[] vis = ``new` `Boolean[n];`
`        ``Arrays.fill(vis, ``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.get(i).getValue() == 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] = ``true``;`

`                ``// move to next node`
`                ``j = arrpos.get(j).getValue();`
`                ``cycle_size++;`
`            ``}`

`            ``// Update answer by adding current cycle.`
`            ``ans += (cycle_size - ``1``);`
`        ``}`

`        ``// Return result`
`        ``return` `ans;`
`    ``}`