CODEWITHSUNDEEP
algorithmcombinations
PSK
PSK

Reputation: 45

How to generate Gray codes of n bits that have at max k ones?

I understand Gray codes have one bit change between them and how to convert between binary and gray. But given a bit length of n, I want to generate a series of Gray codes (all possible) that have one bit change and have maximum k ones.
Example: Given n = 3 and k = 2
001 011 010 110 100 101

Upvotes: 1

Views: 961

Answers (2)

High Performance Mark
High Performance Mark

Reputation: 78354

I don't believe that it is possible to devise such a code. Here's an informal outline of a proof for the case n=4, k=2. There will be 4 codes with 1 bit set and 6 with 2 bits set.

Start with 0000 (though I don't think it matters where the coding actually starts since a Gray code wraps round). Then the next code will have 1 bit set. The next in sequence must have 2 bits set, the one after that 1 bit, then 2, then 1, then 2, then 1, then 2, and you still have 2 codes with 2 bits set left ...

Upvotes: 1

MirMasej
MirMasej

Reputation: 1622

One possible solution I can think of which is quite different from Gray code generation would be in general:

  • generate all numbers within k (Hamming distance)
  • generate all possible valid combinations of above and pick the longest one(s).

But I don't like it because, you need to store all the numbers in a Set and use try and error.

Upvotes: 1

Related Questions