Valid Pairing of Numbers in Java
Given a list of numbers ranging from "0" to (2 * "N" - 1). The goal is to determine the lowest possible number of swaps required to align each even integer in the list, "E," with ("E" + 1).
Example:
int list = [3, 0, 2, 1]
Output:
The minimum number of swaps required for valid pairing is 1.
Explanation:
For the given list, we must put "0" next to "1" and "2" next to "3". We can also replace "0" with "2" to do this. The New list is then provided by [3, 2, 0, 1]. As a result, the total minimum number of swaps, equals to 1.
Note: In the provided list, there will only be distinct numbers.
Approach: Using Disjoint Sets
Let 'E' be any even number in the provided list. The pair 'E' and 'E' + 1' should be considered the graph's vertex. Since the input list/array has size 2 * "N," there will be "N" vertices in the graph. The necessary vertices must now have their edges connected. If number 'E' is present in one pair and number 'E' + 1 in the other, or vice versa, then there will be an edge connecting the two pairs of numbers (two vertices) in the provided list.
The only thing left for us to do is to count the number of interrelated elements, or distinct groupings of vertices, in the graph. There will only be a minimum of one swap, or "N," which is the total number of connected elements in the graph.
Algorithm:
Step 1: Return 'X' if 'X' equals "PARENT[ X ]".
Step 2: If not, the path reduction technique will be used. Recursively execute the "FIND" function once again using the parameters "PARENT" and "PARENT[ X ]," storing the result in "PARENT[ X ]".
Step 3: Give "PARENT[ X ]" return.
Step 4: Create a vector of size "Num" called "PARENT" and assign a value of "i" to each "i-th" place. Our objective is to create a disconnected initial set of all vertices.
Step 5: To assist in mapping down two numbers in a specific pair, create a hash map called "Map."
Step 6: Proceed to iterate over the provided array or list, "a." (let iterator equal "i")
Step 6.1: Put a[ i ] / 2 in a variable called "N."
Step 6.2: At this point, see if it appears in the "Map" already.
Step 6.2.1: Use Map[Num ] = i / 2 if it is absent.
Step 6.2.2: If not, locate the parent of Map[ Num ] (vertex that contains "Num"), store it in "Vertex1," and the parent of 'i' / 2 (vertex that contains "a[ i ]"), store it in "Vertex2." Finally, set the parent of "Vertex1" to equal "Vertex2."
Step 6.2.3: In the step above, all we're attempting to do is create an edge connecting the necessary vertices (as mentioned in the approach section).
Step 7: To hold the number of connected components, create a variable called "countswap." Set it up with a zero initialization.
Implementation:
FileName: DisjointSets.java
import java.util.ArrayList;
import java.util.HashMap;
import java.io.*;
public class DisjointSets
{
// The function here determines the parent or root node of a connected component that contains a node 'x'.
private static int find(ArrayList<Integer> parent, int t)
{
// Return 'x' if the parent of 'x' is 'x' itself.
if (parent.get(t) == t)
{
return t;
}
// Else, find the parent by making the recursive call one again
parent.set(t, find(parent, parent.get(t)));
return parent.get(t);
}
public static int minSwaps(ArrayList<Integer> a, int num)
{
ArrayList<Integer> parent = new ArrayList<Integer>(num);
// At the beginning, consider every component as if it were disconnected,
// and hence set parent[i] = i for each 'i'.
for (int i = 0; i < num; i++)
{
parent.add(i);
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < 2 * num; i++)
{
// Variable to hold the vertex with the number a[i].
int n = a.get(i) / 2;
// Determine whether or not this vertex is already in the hash map.
// If not, add it to the map and hash the map with the position set to 'i'/2.
if (!map.containsKey(n))
{
map.put(n, i / 2);
}
// Else, create an edge connecting the vertices at 'i'/2 and "map[num]".
else
{
int vertex1 = find(parent, map.get(n));
int vertex2 = find(parent, i / 2);
parent.set(vertex1, vertex2);
}
}
// Variable used to store how many connected components there are in the graph.
int countswap = 0;
// iteration through all possible connected components of root node
for (int i = 0; i < num; i++)
{
if (parent.get(i) == i)
{
countswap = countswap + 1;
}
}
return num - countswap;
}
public static void main(String[] args)
{
ArrayList<Integer> a = new ArrayList<>();
a.add(3);
a.add(0);
a.add(2);
a.add(1);
int num = a.size() / 2;
int minswaps = DisjointSets.minSwaps(a, num);
System.out.println("The minimum number of swaps for the given list is : " + minswaps);
}
}
Output:
The minimum number of swaps for the given list is : 1
Complexity Analysis:
The time complexity is O(N * log(N)), where 'N' is half the size of the given array or list. We are using the "FIND" function on the "PARENT" in addition to iterating through the provided list. The space complexity is O(N), where "N" is half of the array or list's size.
Approach: Greedy Approach
The approach's main idea is to simply swap the numbers if they don't make a valid pair and then count the number of pairs that are not valid, such as "E" isn't next to "E" + 1.
Algorithm:
Step 1: Create a HashMap " Map " to store the number and its position as it appears in the provided list or array.
Step 2: First, set Map[ a[ i ] ] = 'i' for each number in the provided list or array. Here, the letter "i" denotes the position of a specific integer.
Step 3: Create a variable called " COUNT " to count the minimum number of swaps needed to make each pair valid.
Step 4: Go through the "array" repeatedly. (let iterator equal "i")
Step 4.1: Assign the other number that needs to be paired with a[i] to a variable called "Num."
Step 4.2: Store a[i] + 1 in "N" after making sure that a[i] is even.
Step 4.3: In "N," store a[i] - 1.
Step 4.4: Simply proceed after confirming that it is currently in a valid pairing.
Step 4.5: If not, replace a[ i + 1 ] with a[ Map[N] ] and move a [ Map[N] ] to a different location in "Map."
Step 4.6: Add one to the "CountSwap" value.
Step 5: Give "CountSwap" back.
Implementation:
FileName: GreedyValidPair.java
import java.util.ArrayList;
import java.util.HashMap;
import java.io.*;
public class GreedyValidPair
{
public static int Swaps(ArrayList<Integer> a, int num)
{
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 2 * num; i++)
{
map.put(a.get(i), i);
}
// To keep track of the total number of swaps made, countSwap is initialized.
int countSwap = 0;
for (int i = 0; i < 2 * num; i += 2)
{
// It determines if the present element and its neighboring element may form a valid pair for each pair.
// It moves on to the following iteration if they can.
int n;
if (a.get(i) % 2 == 0)
{
n = a.get(i) + 1;
}
// If not, a valid pair is created by switching the second element for its matching one.
else
{
n = a.get(i) - 1;
}
if (a.get(i + 1) == n)
{
continue;
}
int temp = a.get(i + 1);
a.set(i + 1, a.get(map.get(n)));
a.set(map.get(n), temp);
map.put(a.get(map.get(n)), map.get(n));
countSwap = countSwap + 1;
}
return countSwap;
}
public static void main(String[] args)
{
ArrayList<Integer> a = new ArrayList<>();
a.add(3);
a.add(0);
a.add(2);
a.add(1);
int num = a.size() / 2;
int minSwaps = Swaps(a, num);
System.out.println("The minimum number of swaps for the given list is : " + minSwaps);
}
}
Output:
The minimum number of swaps for the given list is : 1
Complexity Analysis:
The time complexity for the above approach is O(N), and the space complexity is O(N), where "N" is half of the array or list's size.