Enumerating all possible combination of values for binary variables

user_7375754 0
Viewed 290

Assume I have n variables that each take on two values: 0 or 1. If I wanted to enumerate all possible combinations of values, that would be 2^n possible combinations. I was wondering how to generate this in a clean and simple way?

Imagine n=4. We would want to produce a numpy array or something similar like the following manually generated example.

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

Note that the ordering matters. The first column always looks at cases for col1 = 0, then moves on to cases where col1 = 1. Then col2 looks at cases where col2 = 0 given that col1 = 0, then col2 = 1 given that col1 = 0, then col2 = 0 given that col1 = 1, and finally col2 = 1 given that col1 = 1. And so on. Basically I would need this kind of ordering approach to hold regardless on n.

Can this be solved through an iterative approach?

enumeration iteration binary arrays python
3 Answers

itertools.product([0, 1], repeat=4) will give an iterator that produces such a sequence. np.array(list(itertools.product([0, 1], repeat=4))) will give you a numpy array.

user_2404430

Here's a purely numpy solution:

import numpy as np


def bin_array(n):
    numbers = np.arange(2 ** n).reshape(2 ** n, 1)
    exponents = (2 ** np.arange(n))[::-1]
    return ((exponents & numbers) > 0).astype(int)


print(bin_array(4))

Walkthrough with n = 3

numbers will become:

[[0]
 [1]
 [2]
 [3]
 [4]
 [5]
 [6]
 [7]]

exponents will become:

[4 2 1]

(exponents & numbers) applies bitwise-and from each row in numbers to all of exponents:

[[0 0 0]
 [0 0 1]
 [0 2 0]
 [0 2 1]
 [4 0 0]
 [4 0 1]
 [4 2 0]
 [4 2 1]]

((exponents & numbers) > 0).astype(int) reduces this to zero and ones:

[[0 0 0]
 [0 0 1]
 [0 1 0]
 [0 1 1]
 [1 0 0]
 [1 0 1]
 [1 1 0]
 [1 1 1]]
user_32805380

Well, that's just iterating over the number from 0 to 2^n and printing then in binary notation, so I guess this would work in a simple iterative way:

n = int(input())

for i in range(0, pow(2, n)):
    cur = ""
    for j in range(0, n):
        if i & (1 << j): # If the bit is on add '1' to the string
            cur = cur + '1'
        else:
            cur = cur + '0' # If the bit is off add '0' to the string
    print(cur[::-1]) # Reverse the resulting string
user_67725350
Related