team pair issue

[John Ken]

We have a list of pair{i,j} of teams where i and j are the
teams who will play their first match together in the tournament.There are 2*N teams numbered 0 to 2*N-1.management wants to make this list
good looking before world cup starts .A good looking list has team pairs like {0,1},{2,3},{4,5},{6,7}...{2*N-2,2*N-1) only.
Note that order doesn't matter ,{0,1} nd {1,0} are both valid good looking pair.

Given a list of team pairs,what is the minimum number of team swaps needed to make it a good looking list.

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

Sample Input 1:

3
1 3
0 2
4 5


Sample Output 1:

1

Explanation:

If we swap 0 and 3 list becomes (1,0),(3,2) and (4,5),which is a good looking list.


Sample Input 2:

2
3 2
0 1

Sample Output 2:

0


Explanation:

List is already good looking.

I tried below but could not figure it out neither for sample1 nor for 2 Any suggestions how to correct it to solve both these samples:-

# Python program to find 
# minimum number of swaps 
# required so that 
# all pairs become adjacent. 

# This function updates 
# indexes of elements 'a' and 'b' 
def updateindex(index,a,ai,b,bi): 

	index[a] = ai 
	index[b] = bi 


# This function returns minimum 
# number of swaps required to arrange 
# all elements of arr[i..n] 
# become aranged 
def minSwapsUtil(arr,pairs,index,i,n): 

	# If all pairs procesed so 
	# no swapping needed return 0 
	if (i > n): 
		return 0

	# If current pair is valid so 
	# DO NOT DISTURB this pair 
	# and move ahead. 
	if (pairs[arr[i]] == arr[i+1]): 
		return minSwapsUtil(arr, pairs, index, i+2, n) 

	# If we reach here, then arr[i] 
	# and arr[i+1] don't form a pair 

	# Swap pair of arr[i] with 
	# arr[i+1] and recursively compute 
	# minimum swap required 
	# if this move is made. 
	one = arr[i+1] 
	indextwo = i+1
	indexone = index[pairs[arr[i]]] 
	two = arr[index[pairs[arr[i]]]] 
	arr[i+1],arr[indexone]=arr[indexone],arr[i+1] 

	updateindex(index, one, indexone, two, indextwo) 

	a = minSwapsUtil(arr, pairs, index, i+2, n) 

	# Backtrack to previous configuration. 
	# Also restore the 
	# previous indices, 
	# of one and two 
	arr[i+1],arr[indexone]=arr[indexone],arr[i+1] 
	updateindex(index, one, indextwo, two, indexone) 
	one = arr[i] 
	indexone = index[pairs[arr[i+1]]] 

	# Now swap arr[i] with pair 
	# of arr[i+1] and recursively 
	# compute minimum swaps 
	# required for the subproblem 
	# after this move 
	two = arr[index[pairs[arr[i+1]]]] 
	indextwo = i 
	arr[i],arr[indexone]=arr[indexone],arr[i] 
	updateindex(index, one, indexone, two, indextwo) 
	b = minSwapsUtil(arr, pairs, index, i+2, n) 

	# Backtrack to previous 
	# configuration. Also restore 
	# 3 the previous indices, 
	# of one and two 
	arr[i],arr[indexone]=arr[indexone],arr[i] 
	updateindex(index, one, indextwo, two, indexone) 

	# Return minimum of two cases 
	return 1 + min(a, b) 

# Returns minimum swaps required 
def minSwaps(n,pairs,arr): 

	index=[] # To store indices of array elements 
	for i in range(2*n+1+1): 
		index.append(0) 

	# Store index of each 
	# element in array index 
	for i in range(1,2*n+1): 
		index[arr[i]] = i 

	# Call the recursive function 
	return minSwapsUtil(arr, pairs, index, 1, 2*n) 

# Driver code 

# For simplicity, it is 
# assumed that arr[0] is 
# not used. The elements 
# from index 1 to n are 
# only valid elements 
arr = [0, 3, 5, 6, 4, 1, 2] 

# if (a, b) is pair than 
# we have assigned elements 
# in array such that 
# pairs[a] = b and pairs[b] = a 
pairs= [0, 3, 6, 1, 5, 4, 2] 
m = len(pairs) 

n = m//2 # Number of pairs n 
		# is half of total elements 

# If there are n 
# elements in array, then 
# there are n pairs 
print("Min swaps required is ",minSwaps(n, pairs, arr)) 

[Stephan van Hulst]

CarefullyChooseOneForum <-- read this page

It appears you want to write Python, not Java.

[John Ken]

Stephan van Hulst wrote:CarefullyChooseOneForum <-- read this page <br /> <br /> It appears you want to write Python, not Java.

<br /> <br /> sorry for java i tried below:- <br /> <br />

// Java program to find minimum number 
// of swaps required so that 
// all pairs become adjacent. 

class GFG { 
	
// This function updates indexes 
// of elements 'a' and 'b' 
static void updateindex(int index[], int a, 
					int ai, int b, int bi) 
{ 
	index[a] = ai; 
	index[b] = bi; 
} 

// This function returns minimum number 
// of swaps required to arrange 
// all elements of arr[i..n] become aranged 
static int minSwapsUtil(int arr[], int pairs[], 
					int index[], int i, int n) 
{ 
	// If all pairs procesed so 
	// no swapping needed return 0 
	if (i > n) 
	return 0; 

	// If current pair is valid so 
	// DO NOT DISTURB this pair 
	// and move ahead. 
	if (pairs[arr[i]] == arr[i + 1]) 
	return minSwapsUtil(arr, pairs, index, i + 2, n); 

	// If we reach here, then arr[i] and 
	// arr[i+1] don't form a pair 

	// Swap pair of arr[i] with arr[i+1] 
	// and recursively compute minimum swap 
	// required if this move is made. 
	int one = arr[i + 1]; 
	int indextwo = i + 1; 
	int indexone = index[pairs[arr[i]]]; 
	int two = arr[index[pairs[arr[i]]]]; 
	arr[i + 1] = arr[i + 1] ^ arr[indexone] ^ 
				(arr[indexone] = arr[i + 1]); 
	updateindex(index, one, indexone, two, indextwo); 
	int a = minSwapsUtil(arr, pairs, index, i + 2, n); 

	// Backtrack to previous configuration. 
	// Also restore the previous 
	// indices, of one and two 
	arr[i + 1] = arr[i + 1] ^ arr[indexone] ^ 
				(arr[indexone] = arr[i + 1]); 
	updateindex(index, one, indextwo, two, indexone); 
	one = arr[i]; 
	indexone = index[pairs[arr[i + 1]]]; 

	// Now swap arr[i] with pair of arr[i+1] 
	// and recursively compute minimum swaps 
	// required for the subproblem 
	// after this move 
	two = arr[index[pairs[arr[i + 1]]]]; 
	indextwo = i; 
	arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]); 
	updateindex(index, one, indexone, two, indextwo); 
	int b = minSwapsUtil(arr, pairs, index, i + 2, n); 

	// Backtrack to previous configuration. Also restore 
	// the previous indices, of one and two 
	arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]); 
	updateindex(index, one, indextwo, two, indexone); 

	// Return minimum of two cases 
	return 1 + Math.min(a, b); 
} 

// Returns minimum swaps required 
static int minSwaps(int n, int pairs[], int arr[]) 
{ 
	// To store indices of array elements 
	int index[] = new int[2 * n + 1]; 

	// Store index of each element in array index 
	for (int i = 1; i <= 2 * n; i++) 
	index[arr[i]] = i; 

	// Call the recursive function 
	return minSwapsUtil(arr, pairs, index, 1, 2 * n); 
} 

// Driver code 
public static void main(String[] args) { 
	
	// For simplicity, it is assumed that arr[0] is 
	// not used. The elements from index 1 to n are 
	// only valid elements 
	int arr[] = {0, 3, 5, 6, 4, 1, 2}; 

	// if (a, b) is pair than we have assigned elements 
	// in array such that pairs[a] = b and pairs[b] = a 
	int pairs[] = {0, 3, 6, 1, 5, 4, 2}; 
	int m = pairs.length; 

	// Number of pairs n is half of total elements 
	int n = m / 2; 

	// If there are n elements in array, then 
	// there are n pairs 
	System.out.print("Min swaps required is " + 
					minSwaps(n, pairs, arr)); 
} 
} 

[John Ken]

so any updates by experts please what should i do to get correct input/output for both of these scenarios?

thanks

[Piet Souris]

hi John,

I can't run python code, so I stick to java.

Indeed, your code does not work correctly. I do not know what causes this, but then again, your code is pretty complex to follow. So, to start, I added some print commands to your code, so at least you can follow the development of the array to be swapped. I see no clear development, so you need to add more prints, and use a singlestepper to see if your logic works. Here is that code:

static int minSwapsUtil(int arr[], int pairs[],
    int index[], int i, int n) {
    System.out.println("************ input for minSwapUtils  *************");
    System.out.println("array: " + Arrays.toString(arr));
    System.out.println("pairs: " + Arrays.toString(pairs));
    System.out.println("index: " + Arrays.toString(pairs));
    System.out.format("i = %d  n = %d%n", i, n);
    // If all pairs procesed so 
    // no swapping needed return 0 
    if (i > n) {
        System.out.println("finished");
        return 0;
    }

    // If current pair is valid so 
    // DO NOT DISTURB this pair 
    // and move ahead. 
    if (pairs[arr[i]] == arr[i + 1]) {
        System.out.println("No swapping needed, going to recurse");
        return minSwapsUtil(arr, pairs, index, i + 2, n);
    }

    // If we reach here, then arr[i] and 
    // arr[i+1] don't form a pair 
    // Swap pair of arr[i] with arr[i+1] 
    // and recursively compute minimum swap 
    // required if this move is made. 
    int one = arr[i + 1];
    int indextwo = i + 1;
    int indexone = index[pairs[arr[i]]];
    int two = arr[index[pairs[arr[i]]]];
    arr[i + 1] = arr[i + 1] ^ arr[indexone]
        ^ (arr[indexone] = arr[i + 1]);
    updateindex(index, one, indexone, two, indextwo);
    System.out.println("swapping done, going to recurese");
    int a = minSwapsUtil(arr, pairs, index, i + 2, n);

    // Backtrack to previous configuration. 
    // Also restore the previous 
    // indices, of one and two 
    arr[i + 1] = arr[i + 1] ^ arr[indexone]
        ^ (arr[indexone] = arr[i + 1]);
    updateindex(index, one, indextwo, two, indexone);
    one = arr[i];
    indexone = index[pairs[arr[i + 1]]];

    // Now swap arr[i] with pair of arr[i+1] 
    // and recursively compute minimum swaps 
    // required for the subproblem 
    // after this move 
    two = arr[index[pairs[arr[i + 1]]]];
    indextwo = i;
    arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);
    updateindex(index, one, indexone, two, indextwo);
    int b = minSwapsUtil(arr, pairs, index, i + 2, n);

    // Backtrack to previous configuration. Also restore 
    // the previous indices, of one and two 
    arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);
    updateindex(index, one, indextwo, two, indexone);

    // Return minimum of two cases 
    return 1 + Math.min(a, b);
}

Here is a version that is somewhat simpler than yours. It does not use recursion, but the idea is the same. I have an array, next I make a map (dictionary in python) with keys the values of the array and values the indices of the elements in that array.

I have also a method that, given an index and the array value, determines what the next element should be. For instance, if arr[0] = 4, then we know that arr[1] must be 5, and if arr[0] = 5, then arr[1] must be 4. If arr[1] = 12, then I look up the index of 5, swap the elements 5 and 12, and also adjust the indices-map.  Maybe it is a help to spot the bug in your code. Succes!

public class JohnKen {

    public static void main(String... args) {
        int n = 20;
        var r = new Random();
        int[] a = r.ints(0, n).distinct().limit(n).toArray();
        int result = solve(a);
        System.out.println("took "+ result + " swap" + (result == 1 ? "" : "s"));
    }

    private static int solve(int[] a) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) map.put(a[i], i);
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i += 2) {
            int nextShouldBe = next(a[i], i);
            if (nextShouldBe == a[i + 1]) continue;
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, a[i + 1], nextShouldBe);
            swapArrayElements(a, i + 1, index);
            result++;
            System.out.println(Arrays.toString(a));
        }
        return result;
    }

    private static int next(int nr, int index) {
        if (index % 2 != 0) return Integer.MIN_VALUE;
        return nr % 2 == 0 ? nr + 1 : nr - 1;
    }

    private static void swapIndicesMap(Map<Integer, Integer> map, int i, int j) {
        // using map.replace was unriliable
        int vi = map.get(i);
        int vj = map.get(j);
        map.remove(i);
        map.remove(j);
        map.put(i, vj);
        map.put(j, vi);
    }

    private static void swapArrayElements(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

[John Ken]

Thanks,but both of your code snippets don't get compiled and don't give desired inputs/outputs for below conditions:-

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

Sample Input 1:

3
1 3
0 2
4 5


Sample Output 1:

1

Explanation:

If we swap 0 and 3 list becomes (1,0),(3,2) and (4,5),which is a good looking list.


Sample Input 2:

2
3 2
0 1

Sample Output 2:

0


Explanation:

List is already good looking.

[John Ken]

any updates by java experts please?

Thanks

[Piet Souris]

My code snippets work for me, without a hiccup, and my code is giving correct outcomes. What compile errors do you get?

I added some println's to your code, so that you can follow the development of your given array, so that with some luck you can see what is going wrong with your code, giving you a clue where to look for it.

Your code needs much more explanation for me to understand. What is the idea behind the pairs-array? Why do things need to be reset after recursion? What is the meaning of this cryptic line:

arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);

A problem I have is that I cannot run your code, because I do not understand how to form the pairs array from the given array.

How do you debug your code?

[John Ken]

Piet Souris wrote:My code snippets work for me, without a hiccup, and my code is giving correct outcomes. What compile errors do you get?

I added some println's to your code, so that you can follow the development of your given array, so that with some luck you can see what is going wrong with your code, giving you a clue where to look for it.

Your code needs much more explanation for me to understand. What is the idea behind the pairs-array? Why do things need to be reset after recursion? What is the meaning of this cryptic line:

arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);

A problem I have is that I cannot run your code, because I do not understand how to form the pairs array from the given array.

How do you debug your code?

please find screenshot of errors attached for the code with classname 'JohnKen'

[John Ken]

just missed attachment in previous post please find it attached here.

[Piet Souris]

I didn't mention the required imports. Normally, an IDE will do the imports for you at the click of a mousebutton. Here are the imports:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

[John Ken]

Piet Souris wrote:I didn't mention the required imports. Normally, an IDE will do the imports for you at the click of a mousebutton. Here are the imports:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

ok,thanks,but were you able to run any of below scenarios successfully:-

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

Sample Input 1:

3
1 3
0 2
4 5


Sample Output 1:

1

Explanation:

If we swap 0 and 3 list becomes (1,0),(3,2) and (4,5),which is a good looking list.


Sample Input 2:

2
3 2
0 1

Sample Output 2:

0


Explanation:

List is already good looking.

[Piet Souris]

Yes, I ran all your testcases and it gave the correct result. If you want to try it yourself:

in main() I create an array a, of size n, containing the numbers 0 to (n-1) in random order, and then I call 'solve(a)'. That method does the swaps, prints the array after each swap (so that you can see whether the swaps are correct), and reports the required number of swaps. Not according to the requirements of the exercise, but that was not my goal.

If you want to test your own array, then you can do it as follows:

public static void main(String... args) {
//    int n = 20;
//    var r = new Random();
//    int[] a = r.ints(0, n).distinct().limit(n).toArray();
    int[] a = {1, 3, 0, 2, 4, 5};
    int result = solve(a);
    System.out.println("took "+ result + " swap" + (result == 1 ? "" : "s"));
}

Outcome:

[1, 3, 0, 2, 4, 5]
[1, 0, 3, 2, 4, 5]
[1, 0, 3, 2, 4, 5]
took 1 swap

(the last line is printed twice)

As you see, I leave out the very first parameter. That is not needed in java, since if a is an array, then a.length gives the arraylength.

[John Ken]

Piet Souris wrote:hi John,

I can't run python code, so I stick to java.

Indeed, your code does not work correctly. I do not know what causes this, but then again, your code is pretty complex to follow. So, to start, I added some print commands to your code, so at least you can follow the development of the array to be swapped. I see no clear development, so you need to add more prints, and use a singlestepper to see if your logic works. Here is that code:

static int minSwapsUtil(int arr[], int pairs[],
    int index[], int i, int n) {
    System.out.println("************ input for minSwapUtils  *************");
    System.out.println("array: " + Arrays.toString(arr));
    System.out.println("pairs: " + Arrays.toString(pairs));
    System.out.println("index: " + Arrays.toString(pairs));
    System.out.format("i = %d  n = %d%n", i, n);
    // If all pairs procesed so 
    // no swapping needed return 0 
    if (i > n) {
        System.out.println("finished");
        return 0;
    }

    // If current pair is valid so 
    // DO NOT DISTURB this pair 
    // and move ahead. 
    if (pairs[arr[i]] == arr[i + 1]) {
        System.out.println("No swapping needed, going to recurse");
        return minSwapsUtil(arr, pairs, index, i + 2, n);
    }

    // If we reach here, then arr[i] and 
    // arr[i+1] don't form a pair 
    // Swap pair of arr[i] with arr[i+1] 
    // and recursively compute minimum swap 
    // required if this move is made. 
    int one = arr[i + 1];
    int indextwo = i + 1;
    int indexone = index[pairs[arr[i]]];
    int two = arr[index[pairs[arr[i]]]];
    arr[i + 1] = arr[i + 1] ^ arr[indexone]
        ^ (arr[indexone] = arr[i + 1]);
    updateindex(index, one, indexone, two, indextwo);
    System.out.println("swapping done, going to recurese");
    int a = minSwapsUtil(arr, pairs, index, i + 2, n);

    // Backtrack to previous configuration. 
    // Also restore the previous 
    // indices, of one and two 
    arr[i + 1] = arr[i + 1] ^ arr[indexone]
        ^ (arr[indexone] = arr[i + 1]);
    updateindex(index, one, indextwo, two, indexone);
    one = arr[i];
    indexone = index[pairs[arr[i + 1]]];

    // Now swap arr[i] with pair of arr[i+1] 
    // and recursively compute minimum swaps 
    // required for the subproblem 
    // after this move 
    two = arr[index[pairs[arr[i + 1]]]];
    indextwo = i;
    arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);
    updateindex(index, one, indexone, two, indextwo);
    int b = minSwapsUtil(arr, pairs, index, i + 2, n);

    // Backtrack to previous configuration. Also restore 
    // the previous indices, of one and two 
    arr[i] = arr[i] ^ arr[indexone] ^ (arr[indexone] = arr[i]);
    updateindex(index, one, indextwo, two, indexone);

    // Return minimum of two cases 
    return 1 + Math.min(a, b);
}

Here is a version that is somewhat simpler than yours. It does not use recursion, but the idea is the same. I have an array, next I make a map (dictionary in python) with keys the values of the array and values the indices of the elements in that array.

I have also a method that, given an index and the array value, determines what the next element should be. For instance, if arr[0] = 4, then we know that arr[1] must be 5, and if arr[0] = 5, then arr[1] must be 4. If arr[1] = 12, then I look up the index of 5, swap the elements 5 and 12, and also adjust the indices-map.  Maybe it is a help to spot the bug in your code. Succes!

public class JohnKen {

    public static void main(String... args) {
        int n = 20;
        var r = new Random();
        int[] a = r.ints(0, n).distinct().limit(n).toArray();
        int result = solve(a);
        System.out.println("took "+ result + " swap" + (result == 1 ? "" : "s"));
    }

    private static int solve(int[] a) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) map.put(a[i], i);
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i += 2) {
            int nextShouldBe = next(a[i], i);
            if (nextShouldBe == a[i + 1]) continue;
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, a[i + 1], nextShouldBe);
            swapArrayElements(a, i + 1, index);
            result++;
            System.out.println(Arrays.toString(a));
        }
        return result;
    }

    private static int next(int nr, int index) {
        if (index % 2 != 0) return Integer.MIN_VALUE;
        return nr % 2 == 0 ? nr + 1 : nr - 1;
    }

    private static void swapIndicesMap(Map<Integer, Integer> map, int i, int j) {
        // using map.replace was unriliable
        int vi = map.get(i);
        int vj = map.get(j);
        map.remove(i);
        map.remove(j);
        map.put(i, vj);
        map.put(j, vi);
    }

    private static void swapArrayElements(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

So answer for the first problem  is '2' as per my code and what answer is coming as per your code for below first problem here in this case ? :-
Given a list of team pairs,what is the minimum number of team swaps needed to make it a good looking list.

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

When I compiled JohnKen class code it gave result like 'took 9 swaps'.
also for the modified minSwapsUtil method in your code there was no such text like min no. of swaps required like it was there in mine ?

[Piet Souris]

Lets leave my code for a while.

I did have a look at your original java code. I said I couldn't run it, because I did not understand how you created the necessary 'pairs' array. You had this example in 'main()' in your code:

    int arr[] = {0, 3, 5, 6, 4, 1, 2}; 
 
    // if (a, b) is pair than we have assigned elements 
    // in array such that pairs[a] = b and pairs[b] = a 
    int pairs[] = {0, 3, 6, 1, 5, 4, 2}; 
    int m = pairs.length; 
 
    // Number of pairs n is half of total elements 
    int n = m / 2; 

I really have no clue why your pairs-array was like that. I just changed that to this array:
int[] pairs = {1, 0, 3, 2, 5, 4}
since that is according to your description. The pairs-to-be are (0, 1), (2, 3) and (4, 5). So, according to your description, pairs[0] must be 1, pairs[1] must be 0, pairs[2] must be 3, et cetera. As you see, I left out a starting zero. With this, and some extra output statements, I ran your code again, and got this outcome:

input array: [0, 3, 1, 2, 0, 5, 4]
************ input for minSwapUtils  *************
array: [0, 3, 1, 2, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 1  n = 6
swapping done, Array is now:
[0, 3, 2, 1, 0, 5, 4]
going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 3  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 5  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 7  n = 6
finished
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]        // where is this coming from?
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 3  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 5  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 7  n = 6
finished
Min swaps required is 1

As you see, it seems to work correctly, albeit that some extra work is done. So, have a look why this extra work is being done.

The disadvantage of your code is that you must first create (manually) this pairs[] array, before you can call the method 'minSwaps'. The pairs can be determined automatically. I gave a description how I did that in one of my posts. For instance, the pairs are (0, 1), (2, 3) et cetera. So, if you have a pair that starts with, say 3, then you know the next number of that pair must be 2. I used for this the method:

private static int next(int nr, int index) {
    if (index % 2 != 0) return Integer.MIN_VALUE;  // method is only used for even indices
    return nr % 2 == 0 ? nr + 1 : nr - 1;
}

My advice is that you use this method instead of the pairs array, or that you create the pairs-array with the help of this method.

[John Ken]

Piet Souris wrote:Lets leave my code for a while.

I did have a look at your original java code. I said I couldn't run it, because I did not understand how you created the necessary 'pairs' array. You had this example in 'main()' in your code:

    int arr[] = {0, 3, 5, 6, 4, 1, 2}; 
 
    // if (a, b) is pair than we have assigned elements 
    // in array such that pairs[a] = b and pairs[b] = a 
    int pairs[] = {0, 3, 6, 1, 5, 4, 2}; 
    int m = pairs.length; 
 
    // Number of pairs n is half of total elements 
    int n = m / 2; 

I really have no clue why your pairs-array was like that. I just changed that to this array:
int[] pairs = {1, 0, 3, 2, 5, 4}
since that is according to your description. The pairs-to-be are (0, 1), (2, 3) and (4, 5). So, according to your description, pairs[0] must be 1, pairs[1] must be 0, pairs[2] must be 3, et cetera. As you see, I left out a starting zero. With this, and some extra output statements, I ran your code again, and got this outcome:

input array: [0, 3, 1, 2, 0, 5, 4]
************ input for minSwapUtils  *************
array: [0, 3, 1, 2, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 1  n = 6
swapping done, Array is now:
[0, 3, 2, 1, 0, 5, 4]
going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 3  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 5  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 3, 2, 1, 0, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 7  n = 6
finished
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]        // where is this coming from?
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 3  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 5  n = 6
No swapping needed, going to recurse
************ input for minSwapUtils  *************
array: [0, 0, 1, 2, 3, 5, 4]
pairs: [1, 0, 3, 2, 5, 4]
index: [1, 0, 3, 2, 5, 4]
i = 7  n = 6
finished
Min swaps required is 1

As you see, it seems to work correctly, albeit that some extra work is done. So, have a look why this extra work is being done.

The disadvantage of your code is that you must first create (manually) this pairs[] array, before you can call the method 'minSwaps'. The pairs can be determined automatically. I gave a description how I did that in one of my posts. For instance, the pairs are (0, 1), (2, 3) et cetera. So, if you have a pair that starts with, say 3, then you know the next number of that pair must be 2. I used for this the method:

private static int next(int nr, int index) {
    if (index % 2 != 0) return Integer.MIN_VALUE;  // method is only used for even indices
    return nr % 2 == 0 ? nr + 1 : nr - 1;
}

My advice is that you use this method instead of the pairs array, or that you create the pairs-array with the help of this method.

But When I am using code suggested by you with class name as 'JohnKen' then I am getting result as 'took 6 swaps' but not the desired answer for below query please refer attached screen shot when i ran your modified code with suggested method  :-
So do you think answer should be 6 for the minimum number of team swaps needed to make it a good looking list considering the given data and this problem ?

and the answer which i got when i ran my code was '2'-for minimum number of team swaps needed to make it a good looking list.

Given a list of team pairs,what is the minimum number of team swaps needed to make it a good looking list.

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

[John Ken]

amazingly when I am running that JohnKen code each time i am getting differnt no. of swaps like took 7,8,9 swaps etc.

please refer attached screen shot for the outputs i received when i ran your suggested code for class JohnKen multiple times (here locally on my system i just changed it's class name currently to JohnKen3 as had multiple versions of same programs in my drive.)

[Piet Souris]

hi John,

that is because each time you run the code a new array is formed, with a different permutation of the numbers 0 - 19. That's why you get a different number of required swaps (the first line of the output is the starting array).
The creation of that array is done like this:

int n = 20;
var r = new Random();
int[] a = r.ints(0, n).distinct().limit(n).toArray();

In general, if you have N pairs, then the maximunm number of swaps will be N - 1, since after N - 1 swaps, the last pair is okay (since there are no more pairs to swap with). And sometimes a pair is already oke, so no swap for that pair is needed.

And this topic was, as far as I am concerned, about getting you code up and running, and not to meet the requirements of the exercise. However, to achieve that is easy. Remove all the println's from the solve method (or from your swapUtils methods), and have this structure:

public static void main(String... args) {
    int[] arr = getInputFromWherever();
    int result = solve(arr);
}

private static int[] getInputFromWherever(){
   ...
}

private static int solve(arr) {
   ...
}

[John Ken]

Piet Souris wrote:hi John,

that is because each time you run the code a new array is formed, with a different permutation of the numbers 0 - 19. That's why you get a different number of required swaps (the first line of the output is the starting array).
The creation of that array is done like this:

int n = 20;
var r = new Random();
int[] a = r.ints(0, n).distinct().limit(n).toArray();

In general, if you have N pairs, then the maximunm number of swaps will be N - 1, since after N - 1 swaps, the last pair is okay (since there are no more pairs to swap with). And sometimes a pair is already oke, so no swap for that pair is needed.

And this topic was, as far as I am concerned, about getting you code up and running, and not to meet the requirements of the exercise. However, to achieve that is easy. Remove all the println's from the solve method (or from your swapUtils methods), and have this structure:

public static void main(String... args) {
    int[] arr = getInputFromWherever();
    int result = solve(arr);
}

private static int[] getInputFromWherever(){
   ...
}

private static int solve(arr) {
   ...
}

So do you think below code will compile and run as per resolution of this probelm to give exact answer min. no of swaps required and other sample input/output?

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class JohnKen4 {
 
    public static void main(String... args) {
        int[] arr = getInputFromWherever();
        int result = solve(arr);          

    }

private static int[] getInputFromWherever(){
 
    	....
            
        }
        
    }
 
    private static int solve(arr) {
     
private static int solve(arr) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) map.put(a[i], i);
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i += 2) {
            int nextShouldBe = next(a[i], i);
            if (nextShouldBe == a[i + 1]) continue;
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, a[i + 1], nextShouldBe);
            swapArrayElements(a, i + 1, index);
            result++;

   
    }
 
    

and what should be filled in the method getInputFromWherever() ?

Thanks

[Piet Souris]

By the look of it that code will compile, with the following remarks:

line 21 must be removed
the methods 'next' and the two 'swapXXX' must be added.
(edit: and check your braces!)
(and another edit: you call the parameter 'arr', but in the body you talk about 'a').
and: the parameter should be called: int[] arr, instead of jusr arr. Java ain't python

I do not know in what form the input is provided to you, but usually it is done in a way that is, to you, equivalent to typing in all the numbers. So, I think it should be like this:

private static int[] getInputFromWherever() {
    Scanner s = new Scanner(System.in);
    int numberOfPairs = s.nextInt();
    int[] array = new int[2 * numberOfPairs];
    for (int i = 0; i < array.length; i++) array[i] = s.nextInt();
    return array;
}

But usually they (the suppliers of the exercise) supply you with a template in which this input is taken care of, and you only need to fill in the 'solve' method. Well, HackerRank works this way.

Edit: I forgot to end the main() method with the printing of 'result'      so please add that to the code!

[John Ken]

ok so completed all this like below :-
Is below code fine to get the answer of given problem:
We have a list of pair{i,j} of teams where i and j are the
teams who will play their first match together in the tournament.There are 2*N teams numbered 0 to 2*N-1.management wants to make this list
good looking before world cup starts .A good looking list has team pairs like {0,1},{2,3},{4,5},{6,7}...{2*N-2,2*N-1) only.
Note that order doesn't matter ,{0,1} nd {1,0} are both valid good looking pair.

Given a list of team pairs,what is the minimum number of team swaps needed to make it a good looking list.

Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.

Output Format:-

Print one integer,that is minimum number of swaps needed to make the list good looking

Sample Input 1:

3
1 3
0 2
4 5


Sample Output 1:

1

Explanation:

If we swap 0 and 3 list becomes (1,0),(3,2) and (4,5),which is a good looking list.


Sample Input 2:

2
3 2
0 1

Sample Output 2:

0


Explanation:

List is already good looking.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class JohnKen4 {
 
    public static void main(String... args) {
        int[] arr = getInputFromWherever();
        int result = solve(arr);          
System.out.println(result);
    }


 private static int[] getInputFromWherever() {
    Scanner s = new Scanner(System.in);
    int numberOfPairs = s.nextInt();
    int[] array = new int[2 * numberOfPairs];
    for (int i = 0; i < array.length; i++) array[i] = s.nextInt();
    return array;
}
   
        
      
   
 
    private static int solve(arr) {
     
private static int solve(arr) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) map.put(a[i], i);
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i += 2) {
            int nextShouldBe = next(a[i], i);
            if (nextShouldBe == a[i + 1]) continue;
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, a[i + 1], nextShouldBe);
            swapArrayElements(a, i + 1, index);
            result++;

   
    }
 
    private static int next(int nr, int index) {
        if (index % 2 != 0) return Integer.MIN_VALUE;
        return nr % 2 == 0 ? nr + 1 : nr - 1;
    }
 private static void swapIndicesMap(Map<Integer, Integer> map, int i, int j) {
        // using map.replace was unriliable
        int vi = map.get(i);
        int vj = map.get(j);
        map.remove(i);
        map.remove(j);
        map.put(i, vj);
        map.put(j, vi);
    }
 
    private static void swapArrayElements(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

[John Ken]

ok after incorporating suggested changes and to get desired output as per probelm compiled below code but got attached errors.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class JohnKen4 {
 
    public static void main(String... args) {
        int[] arr = getInputFromWherever();
        int result = solve(int[] arr);          
System.out.println(result);
    }


 private static int[] getInputFromWherever() {
    Scanner s = new Scanner(System.in);
    int numberOfPairs = s.nextInt();
    int[] array = new int[2 * numberOfPairs];
    for (int i = 0; i < array.length; i++) array[i] = s.nextInt();
    return array;
}
   
        
 	     
private static int solve(int[] arr) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < a.length; i++) map.put(a[i], i);
        System.out.println(Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i += 2) {
            int nextShouldBe = next(a[i], i);
            if (nextShouldBe == a[i + 1]) continue;
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, a[i + 1], nextShouldBe);
            swapArrayElements(a, i + 1, index);
            result++;
   
    }
 
    private static int next(int nr, int index) {
        if (index % 2 != 0) return Integer.MIN_VALUE;
        return nr % 2 == 0 ? nr + 1 : nr - 1;
    }

 private static void swapIndicesMap(Map<Integer, Integer> map, int i, int j) {
        // using map.replace was unriliable
        int vi = map.get(i);
        int vj = map.get(j);
        map.remove(i);
        map.remove(j);
        map.put(i, vj);
        map.put(j, vi);
    }
 
    private static void swapArrayElements(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

[John Ken]

..Any idea/suggestions by experts what is going wrong here please ?


Thanks

[Piet Souris]

There are quite some errors in the code. To name three:

- you define a method like this:   private static int solve(int[] arr) {...}
  and you call it like this: int result = solve(a), where the argument a is an int[].
 
- your braces don't match.

- In the method 'solve', the parameter is called 'arr', but in the body it is called 'a'.


I've a version for you with all the errors removed:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class JohnKen4 {

    public static void main(String... args) {
        int[] arr = getInputFromWherever();
        int result = solve(arr);          
        System.out.println(result);
    }

    private static int[] getInputFromWherever() {
        Scanner s = new Scanner(System.in);
        int numberOfPairs = s.nextInt();
        int[] array = new int[2 * numberOfPairs];
        for (int i = 0; i < array.length; i++) {
            array[i] = s.nextInt();
        }
        return array;
    }

    private static int solve(int[] arr) {
        int result = 0;
        var map = new HashMap<Integer, Integer>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < arr.length - 1; i += 2) {
            int nextShouldBe = next(arr[i], i);
            if (nextShouldBe == arr[i + 1]) {
                continue;
            }
            int index = map.get(nextShouldBe);
            swapIndicesMap(map, arr[i + 1], nextShouldBe);
            swapArrayElements(arr, i + 1, index);
            result++;
        }
        return result;
    }
    
    private static int next(int nr, int index) {
        if (index % 2 != 0) {
            return Integer.MIN_VALUE;
        }
        return nr % 2 == 0 ? nr + 1 : nr - 1;
    }

    private static void swapIndicesMap(Map<Integer, Integer> map, int i, int j) {
        // using map.replace was unriliable
        int vi = map.get(i);
        int vj = map.get(j);
        map.remove(i);
        map.remove(j);
        map.put(i, vj);
        map.put(j, vi);
    }

    private static void swapArrayElements(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

If you like, you can translate this code to python, and compare the results.

[John Ken]

Thanks,But after compiling when i am executing it is not showing any result.please see attached screen shot which displays that command prompt stopped when i ran command java JohnKen4 to execute it after compiling this code.

I hope if it runs successfully then i would be able to see desired outputs.


also to convert this code in Python do we have any ready made online tool which could quickly convert it in Python

[John Ken]

John Ken wrote:Thanks,But after compiling when i am executing it is not showing any result.please see attached screen shot which displays that command prompt stopped when i ran command java JohnKen4 to execute it after compiling this code.

I hope if it runs successfully then i would be able to see desired outputs.


also to convert this code in Python do we have any ready made online tool which could quickly convert it in Python

Sorry,after carefully checking found that it will take input but when i gave inputs as shown in screen shot then getting result 0 as shown in screen shot.

[Piet Souris]

First, I see that there is a System.out.println(array) still in the code. To meet the requirements of the exercise, that line must be removed: only the result must be displayed.

Your two examples are already 'good', so no swaps needed.

To make it yourself a bit easier, you can stick to the input as specified in the exercise. So, input:
3
4 0
1 2
3 5