Rob Rob - 1 year ago 104
Python Question

Descartes product with repetition

So i wanted to make a function that takes positive integer

and returns bunch of
, filled with all possible combinations of
True/False (1/0)
, for example:

f(1) = (0,),(1,)

f(2) = (0, 0), (0, 1), (1, 0), (1, 1)

My code was:

def fill(n: int) -> Tuple[Tuple[int]]:
if n == 1:
return (0,),(1,)
return tuple((i + j) for i in fill(n-1) for j in fill(1))

I've heard python isn't very good with recursion, and generally feel this isn't effective solution.

It seemed like using powerset of a range of a given number (recipe for powerset is from the
module) and then using some kind of Indicator function would do the thing.

from itertools import chain, combinations

def range_powerset(n: int):
s = list(range(n))
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def indicator(A: Iterable, B: Iterable):
return tuple(i in A for i in B)

def fill2(n: int):
return (indicator(i, range(n)) for i in range_powerset(n))

Yet it seems like too much work for a pretty basic thing.
Is there a better way to do it?

Answer Source

What you describe is not a powerset but a Descartes product with repetition. Use itertools.product:

import itertools
def fill(n):
    return itertools.product((0,1), repeat=n)


# [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download