Re: Enumerating combinations so that consecutive combinations have a Hamming distance of two?

On Sat, 29 Dec 2007 09:14:32 +0200, Sebastian von Knorring
<Sebastian.von.Knorring@xxxxxx> wrote:


Hello.

I have a programming problem regarding enumeration of combinations. My
problem in a simplified form is as follows:

There are five boxes that can hold one ball each. Two balls are placed
in two of the boxes, the remaining three boxes are left empty. Basic
combinatorics say that the two balls can be placed in the five boxes in
"5 choose 2" = 10 different ways.

Now I wish to enumerate through all the ten possible ball placement
combinations in such a way that at each combination only one ball is
picked up from its box and placed in another empty box, resulting in the
next unseen combination.

Seems like you could do this recursively, _if_ you make the routine
do a little more than just generate such a list - you need a routine
that will generate such a list, _starting_ with _any_ given
combination:

Erase the first element.
Generate all permutations of what's left.
Add the first element back to those permutations.
Erase the first element of the last list you have so far.
Generate all permutations of the right sub-list again.
Put the new first element back in place.
Combine the two results and return.

A Python implementation seems to work:

#start Python code

"""The problem: Given n and k, generate a list of
all ways of putting k things in n boxes, _with_
the property that each one is generated from the
previous via a single swap.

Solution: recursion, _with_ a routine that not
only does the above, it does the above _starting_
with any combination."""

def swap(alist, j, k):
#start by making a copy of alist:
res = alist[:]

#swap two entries and return:
res[j], res[k] = res[k], res[j]
return res

def combs(alist):
"""alist is a list of 0's and 1's
containing k 1's. combs(alist) returns
a list of lists, containing every
list with k 1's, with that Hamiltonianish
property """

#Start by finding the index of the first
#element of alist that is not equal to
#the first (0-th) element. The index
#method raises an exception if there
#is no such element. If there is no
#such element k = 0 or n so we're done.
#SO, look for that index, and if the
#search raises an exception return
#the right thing:

try:
first = alist[1:].index(1-alist[0])
except:
return [alist]

#If we get here the search succeeded.
#now erase the first element of alist
#and generate all the required permutations
#of the remaining list of n-1 elements:

sub = alist[1:]
right = combs(sub)

#now prepend alist[0] back onto the elements of right:

res = map(lambda x, first = alist[0]: [first] + x, right)

#(that looks a little funny because of Python 1.* curious
#scoping rules...)

# now find the first element of the _last_ permutation
#on our result so far that's not equal to alist[0]:

first = res[-1].index(1-alist[0])

#swap the first element and that element:

startover = swap(res[-1], 0, first)

#now start over, erasing the first element of
#startover and generating all the permutations
#you want of the resulting list, then prepending
#startover[0]:

sub = startover[1:]
right = combs(sub)
lasthalf = map(lambda x, first = startover[0]: [first] + x, right)

return res + lasthalf


def printlist(alist):
"""An awesomely clever utility"""
for x in alist:
print x

#end of Python code

If I say printlist(combs([0,0,0,1,1,1])) I get output

[0, 0, 0, 1, 1, 1]
[0, 0, 1, 0, 1, 1]
[0, 0, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 0]
[0, 1, 0, 1, 1, 0]
[0, 1, 0, 1, 0, 1]
[0, 1, 0, 0, 1, 1]
[0, 1, 1, 0, 0, 1]
[0, 1, 1, 0, 1, 0]
[0, 1, 1, 1, 0, 0]
[1, 0, 1, 1, 0, 0]
[1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 0, 1]
[1, 0, 0, 1, 0, 1]
[1, 0, 0, 1, 1, 0]
[1, 0, 0, 0, 1, 1]
[1, 1, 0, 0, 0, 1]
[1, 1, 0, 0, 1, 0]
[1, 1, 0, 1, 0, 0]
[1, 1, 1, 0, 0, 0]

which looks like what we want, although I haven't
inspected it too carefully. Similarly
printlist(combs([0,0,0,1,1])) gives

[0, 0, 0, 1, 1]
[0, 0, 1, 0, 1]
[0, 0, 1, 1, 0]
[0, 1, 0, 1, 0]
[0, 1, 0, 0, 1]
[0, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 0, 0, 1]
[1, 1, 0, 0, 0]

Python's great, btw: Once I figured out what the
algorithm should be I wrote the code about as fast
as I can type, came out with one typo and one
small bug.

After some trial and error, I came up with the following sequence:

_ _ _ X X
_ _ X _ X
_ X _ _ X
X _ _ _ X
X _ _ X _
X _ X _ _
X X _ _ _
_ X X _ _
_ X _ X _
_ _ X X _


A nice property of the sequence above is that it is cyclic, i.e. the
last combination can be transformed back into the first one using the
same rule.

Below is another sequence I worked out by hand, "6 choose 3" = 20. It is
also cyclic.

X X X _ _ _
X X _ X _ _
X X _ _ X _
X X _ _ _ X
X _ X _ _ X
X _ X _ X _
X _ X X _ _
X _ _ X X _
_ X _ X X _
_ X X _ X _
_ X X _ _ X
_ _ X X _ X
_ X _ X _ X
X _ _ X _ X
X _ _ _ X X
_ X _ _ X X
_ _ X _ X X
_ _ _ X X X
_ _ X X X _
_ X X X _ _


My question now is, how can sequences like this be generated
algorithmically? By what rule should the balls be picked up and placed
into the boxes, for all the combinations to appear in sequence? Can all
"M choose N" combinations be enumerated in sequences like this? How many
distinct sequences exist for a given "M choose N"? Are the sequences
always cyclic?


Interpreting the combinations as bit arrays, it can be stated that the
arrays in the sequence have all equal Hamming weight but consecutive
arrays have a Hamming distance of two.

The combinations can also be perceived as nodes in a graph. There is an
edge between two nodes if the combinations have a Hamming distance of
two. In the first ("5 choose 2" = 10) example above, at each row the
next combination can be produced by taking either of the two balls and
placing it into one of the three empty boxes. In other words, of all the
nine other possible combinations that exist, there are 2 x 3 = 6
combinations that are of Hamming distance two and thus neighbors in the
graph. The remaining three combinations are of Hamming distance four and
consequentially neighbors of neighbors in the graph. And this holds for
each node in the graph. As I have understood, this property makes all
graphs of this kind strongly regular graphs. Enumerating all the
combinations in order would then be equal to finding a Hamiltonian path
(or even cycle) for the strongly regular graph in question.


That's what I have come up with until now. Thanks for any pointers to
literature or other insight you might have.


-Sebastian


************************

David C. Ullrich
.

Relevant Pages

  • Re: Scheme as a religion
    ... > parentheses are great for deliminating things, ... first element of the list they start, which determines what is going to ... Programs are made up of lists. ... 'if' is not a operator or a function, but a special form. ...
    (comp.lang.scheme)
  • Re: A way to re-organize a list
    ... I have a simple list reconstruction problem, ... and then by the first element. ... This does one more "list" step, but if your lists aren't huge the ... readability may be worth the small slow-down. ...
    (comp.lang.python)
  • IllegalArg vs NullPtr Exceptions
    ... The utility accepts Lists as arguments to several public methods. ... NullPointerException or NoSuchElementException will be thrown, ... do is invoke List's iterator method. ... Iterator next method for the first element, ...
    (comp.lang.java.programmer)
  • Re: Algorithm for inserting numbers in a list?
    ... such that the number assigned to the first element ... The requirement that the ascending ... One solution might be to use a numbering system like used in the FOCAL ... use "skip lists" to do so. ...
    (comp.theory)