An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm

Consider combinations of \(k\) out of \(n\) items as represented by bit-strings of length \(n\) with exactly \(k\) ones. An algorithm for generating all such combinations so that successive bit-strings differ by the interchange of a single \(01\) or \(10\) pair exists only if \(n\) is even and \(k\) is odd (except for the trivial cases where \(k = n, n-1, 0, 1\)). This was shown by Eades, Hickey, and Read \([4]\) (and others) but no explicit algorithm was given. Later, Carkeet and Eades \([3]\) gave an inefficient, exponential storage implementation. Here, we present an implementation of the algorithm of \([4]\) that is constant average time, and uses linear storage.