Suppose you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, there is a blue jug for every red jug that holds the same amount of water and vice versa. The task is to efficiently group the jugs into pairs of red and blue jugs that hold the same amount of water. (Problem Source: CLRS)
A simple solution to group the jugs into pairs is to compare a red jug with each blue jug. Once we get the matching pair, group that pair, and repeat for the next red jug. This algorithm can be easily implemented, but it will perform at most n2 comparisons.
We can do better by using a randomized algorithm where the expected number of comparisons is nlog(n). The idea is analogous to the randomized quicksort algorithm.
The expected number of comparisons performed by the above algorithm is the same as that of a randomized quicksort algorithm. ie. nlog(n). In the worst case, the largest jug gets picked every time, which results in n2 comparisons.
Below is the implementation in C++, Java, and Python based on the above idea.
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
// Utility function to print an array
void printArray(int arr[], int n, string msg)
{
cout << msg << ” : “;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” “;
}
cout << endl;
}
// This function is similar to the partition routine of the QuickSort algorithm.
// It partitions the specified array `A[low,high]` around the pivot `pivot`
// and returns the partition index.
int partition(int A[], int low, int high, int pivot)
{
int pIndex = low;
for (int j = low; j < high; j++)
{
if (A[j] < pivot)
{
swap(A[pIndex], A[j]);
pIndex++;
}
else if (A[j] == pivot)
{
swap(A[j], A[high]);
j—;
}
}
swap(A[pIndex], A[high]);
return pIndex;
}
// Group the jugs into pairs of red and blue jugs that hold the same amount of water.
// This function is similar to the QuickSort algorithm.
void findMatchingPairs(int red[], int blue[], int low, int high)
{
// base case: if there is only one red jug and one blue jug,
// they must be of the same size
if (low >= high) {
return;
}
// Randomly select a jug from either red jugs or blue jugs
int r = rand() % (high – low + 1) + low;
int chosenJug = red[r]; // or use blue[r]
// Partition the red jugs around the chosen jug
int pivot = partition(red, low, high, chosenJug);
// Now partition the blue jugs around the chosen jug
partition(blue, low, high, chosenJug);
// `pivot` now points to an index of the chosen jug in red/blue jugs
// Recur, once the red and blue jugs are divided into two groups
// around the chosen jug
findMatchingPairs(red, blue, low, pivot – 1);
findMatchingPairs(red, blue, pivot + 1, high);
}
int main()
{
int red[] = { 6, 3, 2, 8, 7 };
int blue[] = { 8, 6, 7, 2, 3 };
int n = sizeof(red) / sizeof(red[0]);
findMatchingPairs(red, blue, 0, n – 1);
printArray(red, n, “Red jugs “);
printArray(blue, n, “Blue jugs”);
return 0;
}
|
Output:
Red jugs : 2 3 6 7 8
Blue jugs : 2 3 6 7 8
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.util.Arrays;
import java.util.Random;
public class Main {
// Utility function to swap elements `A[i]` and `A[j]` in the array `A`
public static void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// This method is similar to the partition routine of the QuickSort algorithm.
// It partitions the specified array `A[low,high]` around the pivot `pivot`
// and returns the partition index.
private static int partition(int[] A, int low, int high, int pivot)
{
int pIndex = low;
for (int j = low; j < high; j++) {
if (A[j] < pivot) {
swap(A, pIndex, j);
pIndex++;
} else if (A[j] == pivot) {
swap(A, j, high);
j—;
}
}
swap(A, pIndex, high);
return pIndex;
}
// Group the jugs into pairs of red and blue jugs that hold the same amount of water
// This method is similar to the QuickSort algorithm.
private static void findMatchingPairs(int[] red, int[] blue, int low, int high)
{
// base case: if there is only one red jug and one blue jug,
// they must be of the same size
if (low >= high) {
return;
}
// Randomly select a jug from either red jugs or blue jugs
int r = new Random().nextInt(high – low + 1) + low;
int chosenJug = red[r]; // or use blue[r]
// Partition the red jugs around the chosen jug
int pivot = partition(red, low, high, chosenJug);
// Now partition the blue jugs around the chosen jug
partition(blue, low, high, chosenJug);
// `pivot` now points to an index of the chosen jug in red/blue jugs
// Recur, once the red and blue jugs are divided into two groups
// around the chosen jug
findMatchingPairs(red, blue, low, pivot – 1);
findMatchingPairs(red, blue, pivot + 1, high);
}
public static void main(String[] args)
{
int[] red = {6, 3, 2, 8, 7};
int[] blue = {8, 6, 7, 2, 3};
findMatchingPairs(red, blue, 0, red.length – 1);
System.out.println(“Red jugs : “ + Arrays.toString(red));
System.out.println(“Blue jugs : “ + Arrays.toString(blue));
}
}
|
Output:
Red jugs : [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
import random
# Utility function to swap elements `A[i]` and `A[j]` in the array `A`
def swap(A, i, j):
temp = A[i]
A[i] = A[j]
A[j] = temp
# This method is similar to the partition routine of the QuickSort algorithm.
# It partitions the specified array `A[low, high]` around the pivot `pivot`
# and returns the partition index.
def partition(A, low, high, pivot):
pIndex = low
j = low
while j < high:
if A[j] < pivot:
swap(A, pIndex, j)
pIndex = pIndex + 1
elif A[j] == pivot:
swap(A, j, high)
j = j – 1
j = j + 1
swap(A, pIndex, high)
return pIndex
# Group the jugs into pairs of red and blue jugs that hold the same amount of water.
# This method is similar to the QuickSort algorithm.
def findMatchingPairs(red, blue, low, high):
# base case: if there is only one red jug and one blue jug,
# they must be of the same size
if low >= high:
return
# Randomly select a jug from either red jugs or blue jugs
r = random.randint(low, high)
chosenJug = red[r] # or use blue[r]
# Partition the red jugs around the chosen jug
pivot = partition(red, low, high, chosenJug)
# Now partition the blue jugs around the chosen jug
partition(blue, low, high, chosenJug)
# `pivot` now points to an index of the chosen jug in red/blue jugs
# Recur, once the red and blue jugs are divided into two groups
# around the chosen jug
findMatchingPairs(red, blue, low, pivot – 1)
findMatchingPairs(red, blue, pivot + 1, high)
if __name__ == ‘__main__’:
red = [6, 3, 2, 8, 7]
blue = [8, 6, 7, 2, 3]
findMatchingPairs(red, blue, 0, len(red) – 1)
print(“Red jugs :”, red)
print(“Blue jugs :”, blue)
|
Output:
Red jugs : [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]
Download Run Code
Output:
Red jugs : 2 3 6 7 8
Blue jugs : 2 3 6 7 8
Download Run Code
Output:
Red jugs : [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]
Download Run Code
Output:
Red jugs : [2, 3, 6, 7, 8]
Blue jugs: [2, 3, 6, 7, 8]
There are several other variations of this problem which can be solved similarly: