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

Tim Hough, Department of Computer Science, University of California, San Diego.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


Consider combinations of k out of n items as represented by bitstrings of length n with exactly k ones. An algorithm for generating all such combinations so that successive bitstrings 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 [EHR] (and others) but no explicit algorithm was given. Later Carkeet and Eades [CE] gave an inefficient, exponential storage implementation. Here we present an implementation of the algorithm of [EHR] that is constant average time, and uses linear storage.

Selected papers that refer to this one:
Back to list of publications.