Find all combinations of 0, 1 that sum to 1 or 2 at varying lengths / sizes

Question

I would like a function that would return 0, 1 combinations, that sum to 1 or 2, for varying length. I know the total combinations (before removing the summations) follow 2**length.

Example: length = 4

Result:

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

I was able to use a recursive function to get up to lengths of 10. After that, python crashes due to recursion limit.

I did try increasing it, but this still results in the program crashing. I would like to be able to do all combinations that sum to 1 or 2 up to a length of 40.

That code is listed below:

def recursive_comb(bits):
     """Creates all possible combinations of 0 & 1
     for a given length
     """
     test = []

     def calc_bits(bits, n=0):
         if n.bit_length() <= bits:
             comb_str = '{:0{}b}'.format(n, bits)
             comb_list = [int(elem) for elem in comb_str]
             test.append(comb_list) 
             calc_bits(bits, n + 1)

     calc_bits(bits)

     return test

all_comb = recursive_comb(4)

all_comb = [elem for elem in all_comb if ((sum(elem) == 1) or (sum(elem) == 2))]

Answer 1

if you don't mind using an external library (sympy) you could use this:

from sympy.utilities.iterables import multiset_permutations

length = 4
for n in range(1, 3):
    lst = [1] * n + [0] * (length - n)
    for perm in multiset_permutations(lst):
        print(perm)

multiset_permutations generates all distinct permutations of a list with elements that are not pairwise different. i use this for lists with the desired numbers of 0 and 1.

if your lists contain many elements this will be much more efficient that just go through all possible permutations and discard the duplicates using a set.