Previous: Stable Marriage algorithm Up: The pairing step Next: Hungarian algorithm

Brute force

While searching for a replacement for the stable marriage algorithm, a simple brute force algorithm was written. This algorithm was written in order to allow a check of the results of other algorithms. It is not a very efficient algorithm, neither in theory, nor in implementation. It has a running time of .

The algorithm treats each possible combinations as a bit in a number. Each bit is either on or off, depending on whether that pair is to be included or excluded.

All combinations of bits are enumerated by treating the bit-stream as a binary number and counting. Many patterns are not valid: not all quarks are paired to exactly one antiquark. Valid combinations have their distance totaled, and compared to a current minimum. If the value is smaller, then that combination is kept.

The algorithm could be made by enumerating only valid combinations. However, by Stirling's approximation [4][page 35], so asymptotically, it isn't much better.