Алгоритм, чтобы получить все возможные подмножества списка, в порядке их продукта, без построения и сортировки всего списка (т.е. генераторы) - PullRequest
Новая
       18

Алгоритм, чтобы получить все возможные подмножества списка, в порядке их продукта, без построения и сортировки всего списка (т.е. генераторы)

4 голосов
/ 25 февраля 2011

Практически, у меня есть набор объектов с вероятностями, и я хочу посмотреть на каждую возможную группу из них, в порядке вероятности того, что они все истинны, предполагая, что они 'независимы - т.е. в порядке убывания произведения элементов подмножеств - или в порядке длины, если вероятности одинаковы (так что (1, 0,5) следует после (0,5)).

Пример: если у меня есть [ 1, 0.5, 0.1 ], я хочу [ (), (1), (0.5), (1, 0.5), (0.1), (1, 0.1), (0.5, 0.1), (1, 0.5, 0.1) ]

По сути, это означает, что я хочу перебирать набор элементов по порядку, и я мог бы довольно легкосгенерируйте это, сортируйте это и делайте.Однако наборы мощности становятся довольно большими и довольно быстрыми, я ожидаю, что обычно мне понадобится один из первых подмножеств, и я бы предпочел не генерировать список из тысяч подмножеств, сортировать их, а затем никогда не заглядывать за третье.Вот где, надеюсь, генераторы python спасут день!

Более формальная спецификация проблемы, мне нужно найти способ сделать sorted(powerset(input), key = lambda l : reduce (lambda (p, n), e: (p * e, n-1), l, (1, 0)), reverse=True) в качестве генератора или каким-либо другим способом, который позволит мне избежать сборкии сортировка всего списка.

Я вполне уверен, что это связано с проблемой ранца, наряду с проблемой подмножества продуктов, но я действительно изо всех сил пытаюсь получить хороший алгоритм для него, который работает, и помогитебыл бы очень признателен :-).Это не проблема для того, чтобы он был медленнее, чем сборка + сортировка всего в худшем случае (итерация до конца), ему просто нужно намного лучшее выполнение (в пределах, скажем, первых 10%).

1 Ответ

5 голосов
/ 25 февраля 2011

Хороший вопрос, решить его было довольно сложно. Я также не могу придумать способ генерирования комбинаций по порядку, но я использую могущественный heapq (он же приоритетная очередь), чтобы сохранить кандидатов отсортированными. 

from heapq import heappush, heappop
import operator

def prob(ps):
    """ returns the probability that *not* all ps are True """
    return 1-reduce(operator.mul, ps)

def gen(ps):
    # turn each to a tuple
    items = ((x,) for x in sorted(ps, reverse=True))

    # create a priority queue, sorted by probability
    pq = [(prob(x),x) for x in items]

    # because you wanted this
    yield ()

    # as long as there are valid combinations
    while pq:
        # get the best un-yielded combination, the pq makes sure of that
        p, x = heappop(pq)
        yield x

        # generate all the combinations from this item
        for other in ps:

            # keeping the tuples sorted -> unique combinations
            if other < x[-1]:

                # create a new combination
                new = x+(other,)
                item = prob(new), new

                # add it to the queue
                heappush(pq,item)


a = [1, 0.1, 0.5] 
print list(gen(a))
...