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

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))]

CodePudding user response：

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.

CodePudding user response：

You could simply do it like this:

from itertools import permutations

length = 4
result = {p for p in permutations([0, 1]*length, length) if sum(p) in [1, 2]}

print(result)

# output:
# {(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)}

The resulting set contains all permutations that sum up to 1 or 2.

There is some redundant computations done in permutations, so it may take a while depending on length, but you shouldn't run into recursion / memory errors.