Генерация всех возможных подмножеств данного QuerySet в Django - PullRequest
Новая
       5

Генерация всех возможных подмножеств данного QuerySet в Django

1 голос
/ 12 апреля 2010

Это только пример, но с учетом следующей модели: 

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

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

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

И следующий QuerySet объект: 

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

(имеется в виду набор уникальных Foo моделей с bar <= 20), как я могу сгенерировать все возможные подмножества foobar? В идеале я хотел бы дополнительно ограничить подмножества, чтобы для каждого подмножества x из foobar сумма всех f.bar в x (где f - модель типа Foo) находится между некоторым максимальным и минимальным значением.

Так, например, с учетом следующего экземпляра foobar: 

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

И min=5, max=25, я хотел бы построить объект (предпочтительно QuerySet, но, возможно, список), который выглядит следующим образом: 

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

Я экспериментировал с itertools, но он не очень подходит для моих нужд.

Я думаю это можно сделать с помощью комплекса QuerySet, но я не знаю, с чего начать.

Ответы [ 2 ]

3 голосов
/ 12 апреля 2010 
S = [list(itertools.combinations(foobar,i)) for i in xrange(1, len(foobar))]

Создает неплоский список. Вы можете сгладить это: 

list(itertools.chain.from_iterable(S))
1 голос
/ 12 апреля 2010

Это даст вам powerset из foobar (как список) 

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

Добавление фильтра для minval и maxval дает: 

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]

Давайте создадим класс и попробуем его 

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

Если вам нужны списки, а не кортежи, добавить это тоже тривиально 

>>> [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>]]
...