CODEWITHSUNDEEP
pythonalgorithmcombinationsgray-code
Curious
Curious

Reputation: 557

k-combination of n items with "Gray code"-like property

I already know how to generate k combinations of n values as described here https://stackoverflow.com/a/28698654/15853075. The problem is that I need one additional property: I want each pair of successive combinations to differ only at one position (or have "Gray code"-like property). It doesn't matter if it is done during construction or uses a special sorting rule after all combinations are generated.

For example, the original implementation with k=3, n=5 produces the following sequence

 0 1 2
 0 1 3 <- good, previous line differs only in the last position (2->3)
 0 1 4
 0 2 3 <- bad, there are two changes (1->2) and (4->3)
 0 2 4
 0 3 4
 1 2 3
 1 2 4
 1 3 4
 2 3 4

Instead, I want to see something like this (there can be multiple solutions that satisfy "Gray code"-like property).

 0 1 2
 0 1 3 
 0 2 3
 0 2 4
 0 1 4
 0 3 4
 2 3 4
 1 3 4
 1 2 4
 1 2 3

It seems that it is possible to keep all numbers inside the combination sorted (1 0 2 should not occur, only 0 1 2 is allowed).

Update

The answer by @Stef shows a solution with the sequence of numbers below. It fails to satisfy the single change property if we consider changes in different columns independently.

0, 1, 2
0, 2, 3
1, 2, 3
0, 1, 3 <- bad, change 1: (1->0), change 2: (2->1)
0, 3, 4
1, 3, 4
2, 3, 4
0, 2, 4
1, 2, 4
0, 1, 4

The obvious suggestion to reorder the numbers in a combination (to replace 0 1 3 by 1 0 3) fails to satisfy the sortedness requirement mentioned above.

It is not clear if solution that satisfies this constraint exists for any pair (n, k), but so far I didn't find when it was not possible.

Upvotes: 2

Views: 387

Answers (1)

Stef
Stef

Reputation: 15525

I found the following recurrence formula to generate the list of combinations in Gray-code order:

C(n,k) = C(n-1,k).0 + [C(n-1,k-1)]bar.1

Source: encyclopediaofmaths.org: Gray-code #Combinations

With notations explained:

  • C(n,k) is the list of k-combinations of n elements in Gray-code order;
  • C(n-1,k).0 is just C(n-1,k)
  • [L]bar means "list L in reverse order"
  • L.1 means "the tuples from list L, with n-1 added to each tuple"

With all that in mind, and using python generators, the recurrence formula becomes:

def combinations_graycode(n, k):
    yield from combinations_graycode(n-1, k)
    for comb in reversed(list(combinations_graycode(n-1, k-1))):
        yield comb + (n-1,)

Adding a base-case for the recursion, here is the whole python code:

def combinations_graycode(n, k):
    if k < 0:
        raise ValueError('k must be non-negative')
    elif k > n or n < 1:
        pass
    elif k == 0:
        yield ()
    elif k == n:
        yield tuple(range(n))
    else:
        yield from combinations_graycode(n-1, k)
        for comb in reversed(list(combinations_graycode(n-1, k-1))):
            yield comb + (n-1,)

print(list(combinations_graycode(5, 3)))
# [(0, 1, 2), (0, 2, 3), (1, 2, 3), (0, 1, 3), (0, 3, 4), (1, 3, 4), (2, 3, 4), (0, 2, 4), (1, 2, 4), (0, 1, 4)]

Upvotes: 2

Related Questions