**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.

*mcr@ccs.carleton.ca*