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

Abstract

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.