Generating all possible subsets of a given QuerySet in Django

Question

This is just an example, but given the following model:

class Foo(models.model):
    bar = models.IntegerField()

    def __str__(self):
        return  str(self.bar)

    def __unicode__(self):
        return str(self.bar)

And the following QuerySet object:

foobar = Foo.objects.filter(bar__lt=20).distinct()

(meaning, a set of unique Foo models with bar <= 20), how can I generate all possible subsets of foobar? Ideally, I'd like to further limit the subsets so that, for each subset x of foobar, the sum of all f.bar in x (where f is a model of type Foo) is between some maximum and minimum value.

So, for example, given the following instance of foobar:

>> print foobar
[<Foo: 5>, <Foo: 10>, <Foo: 15>]

And min=5, max=25, I'd like to build an object (preferably a QuerySet, but possibly a list) that looks like this:

[[<Foo: 5>], [<Foo: 10>], [<Foo: 15>], [<Foo: 5>, <Foo: 10>],
 [<Foo: 5>, <Foo: 15>], [<Foo: 10>, <Foo: 15>]]

I've experimented with itertools but it doesn't seem particularly well-suited to my needs.

I think this could be accomplished with a complex QuerySet but I'm not sure how to start.

Answer 1

S = [list(itertools.combinations(foobar,i)) for i in xrange(1, len(foobar))]

It produces non-flat list. You can flatten it by:

list(itertools.chain.from_iterable(S))

Answer 2

This will give you the powerset of foobar (as a list)

from itertools import combinations
[j for i in range(len(foobar)+1) for j in combinations(foobar,i)]

Adding a filter for the minval and maxval gives:

from itertools import combinations
[j for i in range(len(foobar)+1) for j in combinations(foobar,i)
 if minval <= sum(f.bar for f in j) <= maxval]

Lets create a class and try it out

>>> from itertools import combinations
>>> class Foo(object):
...     def __init__(self, bar):
...         self.bar=bar
...     def __repr__(self):
...         return  "<Foo: %s>"%self.bar
... 
>>> foobar=[Foo(5),Foo(10),Foo(15)]
>>> minval=5
>>> maxval=25
>>> [j for i in range(len(foobar)+1) for j in combinations(foobar,i) 
     if minval <= sum(f.bar for f in j) <= maxval]
[(<Foo: 5>,), (<Foo: 10>,), (<Foo: 15>,), (<Foo: 5>, <Foo: 10>), (<Foo: 5>, <Foo: 15>), (<Foo: 10>, <Foo: 15>)]

If you need lists rather than tuples it's trivial to add that in too

>>> [list(j) for i in range(len(foobar)+1) for j in combinations(foobar,i) if minval <= sum(f.bar for f in j) <= maxval ]
[[<Foo: 5>], [<Foo: 10>], [<Foo: 15>], [<Foo: 5>, <Foo: 10>], [<Foo: 5>, <Foo: 15>], [<Foo: 10>, <Foo: 15>]]