Search code examples
pythonpython-itertools

How to get all combinations of n binary values where number of 1's are equal to or more than the number of 0's?


I want to find a list of all possible combinations of 0's and 1's. The only condition is that the number of 1's must be more than or equal to the number of 0's. For example for n = 4 the output should be something like this:

[(0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (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)]

Is there an elegant way to do this?


Solution

  • You can use distinct_permutations:

    from more_itertools import distinct_permutations
    
    def get_combos(n):
        for i in range((n+1)//2, n + 1):
            for permutation in distinct_permutations([1] * i + [0] * (n - i), n):
                yield permutation
    print(list(get_combos(4)))
    # [(0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0), (0, 1, 1, 1), (1, 0, 1, 1), (1, 1, 0, 1), (1, 1, 1, 0)]
    

    Here, we simply consider the permutations of each sublist:

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

    Notice that for large n, the yield statement is very useful because you do not generate all permutations at once.

    We need to use distinct_permutations because you use just 1's and 0's , so regular permutations will give you repeated elements.


    If you don't want to install another library, you can use:

    from itertools import permutations
    
    def get_combos(n):
        for i in range(n // 2 if n%2 == 0 else n//2 + 1, n):
            for permutation in permutations([1] * i + [0] * (n - i), n):
                yield permutation
    print(set(get_combos(4)))
    # {(0, 1, 0, 1), (0, 1, 1, 1), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 1, 0), (0, 1, 1, 0), (1, 0, 1, 0), (1, 0, 0, 1), (1, 1, 0, 1), (0, 0, 1, 1)}
    

    as set will eliminate the repeated elements, at the cost of needing to process the entire set of permutations at once (ie., by calling set, you will consume the entire generator immediately, rather than drawing elements from it as you need them).

    More details on distinct_permutations

    It might not be clear why these are needed. Consider this list:

    [1, 2]
    

    permutations, by default, will tell you that all the permutations of this list are

    (1, 2)
    

    and

    (2, 1)
    

    However, permutations doesn't bother checking what the elements are or if they are repeated, so it simply performs the swap as above and if the list is

    [1, 1]
    

    you'll get back

    [(1, 1), (1, 1)]