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?
CodePudding user response:
You can use distinct_permutations
:
from more_itertools import distinct_permutations
def get_combos(n):
for i in range((n 1)//2, n):
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)]
CodePudding user response:
You could use itertools.combinations
for choosing k of the n indexes to set to 0:
from itertools import combinations
def get_combos(n):
for k in range(n//2 1):
for indexes in combinations(range(n), k):
combo = [1] * n
for i in indexes:
combo[i] = 0
yield tuple(combo)
print(list(get_combos(4)))
CodePudding user response:
Building up on @Kraigolas excellent answer, we can even simplify the entire process by building one single initial list containing n // 2
zeros (0
) and n
ones (1
). We then get the distinct permutations
of length n
only from that initial list
So for n = 4
we return distinct permutation of size 4 from the following list: [0, 0, 1, 1, 1, 1]
from more_itertools import distinct_permutations
def get_combos(n):
return distinct_permutations([0] * (n // 2) [1] * n, n)
print(list(get_combos(4)))
# [(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)]