0

So i wanted to make a function that takes positive integer n and returns bunch of n-tuples, 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 itertools 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?

Dimitris Fasarakis Hilliard
  • 150,925
  • 31
  • 268
  • 253
Rob
  • 65
  • 5
  • 4
    Did you read https://docs.python.org/3/library/itertools.html#itertools-recipes – jonrsharpe Jul 19 '16 at 13:03
  • Possible duplicate of [Python: powerset of a given set with generators](http://stackoverflow.com/questions/18826571/python-powerset-of-a-given-set-with-generators) – hashcode55 Jul 19 '16 at 13:06
  • This question is probably best suited for [Code Review](http://codereview.stackexchange.com/). – Dimitris Fasarakis Hilliard Jul 19 '16 at 13:06
  • To knelwood: what exactly is not a powerset? if you mean the name of topic, i chose it for lack of a better name, id be glad if you can suggest something else. if you mean function i defined range_powerset, what it returns is basically a powerset, no mistake here. To jonrsharpe: thanks for reminder, did i miss something there? i took powerset recipe there but it wasnt exactly a solution for my task – Rob Jul 19 '16 at 13:07
  • One more possible duplicate http://stackoverflow.com/questions/1482308/whats-a-good-way-to-combinate-through-a-set – hashcode55 Jul 19 '16 at 13:07

1 Answers1

8

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)

print(list(fill(3)))

# [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
Tamas Hegedus
  • 28,755
  • 12
  • 63
  • 97