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