Problem:
Matching nuts and bolts problem can be stated as follows: “Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt.” We can only compare nuts to bolts i.e., we can neither compare nuts to nuts nor bolts to bolts.
If we could compare nuts to nuts and bolts to bolts, we could simply sort both nuts and bolts separately and pair off the nuts and bolts in matching positions. However, since comparing identical items is not allowed, this problem appears to be harder than sorting. As we will soon see, it can indeed be reduced to sorting.
Solution:
The brute-force solution would be to compare each nut with all bolts to find the matching bolt and can be implemented in O(n2). In fact, we can do better than n2 by using a randomized algorithm similar to Quicksort.
We can use quick sort technique to solve this. We represent nuts and bolts in character array for understanding the logic.
Nuts represented as array of character
char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’}
Bolts represented as array of character
char bolts[] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}
This algorithm first performs a partition by picking last element of bolts array as pivot, rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side. Next using the nuts[i] we can partition the array of bolts. Partitioning operations can easily be implemented in O(n). This operation also makes nuts and bolts array nicely partitioned. Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.
Implementation:
Partition(bolts[lo...hi], nut):
j = lo
for i in range(lo, hi):
if bolts[i] < nut:
swap(bolts[i], bolts[j])
j += 1
elif bolts[i] == nut:
swap(bolts[i], bolts[hi])
# the bolt that ends up at i might be larger than nut
i -= 1
swap(bolts[j], bolts[hi])
return j
Similar procedure for partitioning nuts according to a given bolt
Match(nuts[lo...hi], bolts[lo...hi]):
if lo < hi:
# choose a nut in [lo...hi] at random
chosen = nuts[random(lo, hi+1)]
# partition bolts around the chosen nut
pivot = Partition(bolts[lo...hi], chosen)
# partition nuts around the bolt at the pivot position
Partition(nuts[lo...hi], bolts[pivot])
# nut and bolt at the pivot position match
# solve the subproblem [lo...pivot-1] recursively
Match(nuts[lo...pivot-1], bolts[lo...pivot-1])
# solve the subproblem [pivot+1...hi] recursively
Match(nuts[pivot+1...hi], bolts[pivot+1...hi])
Average time complexity = O(nlogn).
Worst time complexity = O(n^2).
Note: If more than one pair of nuts and bolts, we can divide them in 3 parts rather than 2.
