Generate all n-bit binary bit patterns in order of their sum

Question

I need a generator that yields every bit pattern of n bits in order of their sum (and more). For example for n=3,

1. sum([0, 0, 0]) = 0 ✓
2. sum([1, 0, 0]) = 1 ✓
3. sum([0, 1, 0]) = 1 ✓
4. sum([1, 1, 0]) = 2 ⨯  should be swapped with 5.
5. sum([0, 0, 1]) = 1 ⨯
6. sum([1, 0, 1]) = 2 ✓
7. sum([0, 1, 1]) = 2 ✓
8. sum([1, 1, 1]) = 3 ✓

Note that even though 3 and 5 have the same sum, 5 should be generated after 3. The correct order would have been, 000, 100, 010, 001, 110, 101, 011, 111. The idea here is that if this (2ⁿ, n) dimension matrix was multiplied by a (n, 1) vector that is sorted in ascending order than the product would be sorted as well. Eliminating the need to sort this product will help in optimising an experiment I am trying to run.

Here is my rather inefficient and incomplete attempt,

def forwards(n):
    ls = [0]*n
    for i in range(n):
        for j in range(n-i):
            copy = list(ls)
            copy[j] = 1
            yield copy
        ls[-(i+1)] = 1

As you can see, this does get the order right but misses some patterns.

Here is another somewhat efficient but wrong order attempt.

def forwards(n):
    for i in range(1 << n):
        yield [(i >> k) & 1 for k in range(n)]

This one generates all patterns but in the wrong (shown in the example above) order.

I need this function to be efficient so solutions where a string is generated and then characters are converted to integers are discouraged.

Lastly, I am working in Python 3.9. You can use Numpy.

Answer 1

I believe this gives you the order you want:

1. First, sort in ascending order by number of 1's
2. Next, sort in descending order by lexicographical order

from itertools import combinations 

def forwards(n):
  for one_bits in range(n + 1):
    for combination in combinations(range(n), one_bits):
      yield [1 if x in combination else 0 for x in range(n)]

for x in forwards(4):
  print("{}, one bits = {}, binary value = {}".format(x, sum(x), sum(x[i] * 2**(3 - i) for i in range(4))))

This works by handling the first condition in the first for loop for one_bits in range(n + 1):, and generating all possible N-sized combinations of indices between 0 and n - 1, and then those indices are set to 1, else 0.

This prints

[0, 0, 0, 0], one bits = 0, binary value = 0
[1, 0, 0, 0], one bits = 1, binary value = 8
[0, 1, 0, 0], one bits = 1, binary value = 4
[0, 0, 1, 0], one bits = 1, binary value = 2
[0, 0, 0, 1], one bits = 1, binary value = 1
[1, 1, 0, 0], one bits = 2, binary value = 12
[1, 0, 1, 0], one bits = 2, binary value = 10
[1, 0, 0, 1], one bits = 2, binary value = 9
[0, 1, 1, 0], one bits = 2, binary value = 6
[0, 1, 0, 1], one bits = 2, binary value = 5
[0, 0, 1, 1], one bits = 2, binary value = 3
[1, 1, 1, 0], one bits = 3, binary value = 14
[1, 1, 0, 1], one bits = 3, binary value = 13
[1, 0, 1, 1], one bits = 3, binary value = 11
[0, 1, 1, 1], one bits = 3, binary value = 7
[1, 1, 1, 1], one bits = 4, binary value = 15