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.
Abstract:
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.
-
The references above are:
-
P. Eades, M. Hickey and R.C. Read,
Some Hamilton paths and a minimal change algorithm
JACM, 31 (1984) 19-29.
-
M. Carkeet and P. Eades,
A subset generation algorithm with a very strong minimal
change property, Congressus Numerantium, 47 (1985) 139-143.
-
Downloads:
-
Appeared in Journal of Combinatorial Mathematics and Combinatorial Computing,
4 (1988) 79-86.
-
Tim Hough
is currently(?) with the Lawerence Livermore Labs.
Selected papers that refer to this one:
-
Moshe Schwartz,
Constant-Weight Gray Codes for Local Rank Modulation,
IEEE International Symposium on Information Theory, ISIT 2010,
pg. 869-873.
Back to list of publications.