Найти все возможные подмножества, которые суммируют до заданного числа - PullRequest
Новая
       10

Найти все возможные подмножества, которые суммируют до заданного числа

2 голосов
/ 30 ноября 2011

Я изучаю Python, и у меня проблема с этим, кажется, простая задача.

Я хочу найти все возможные комбинации чисел, которые суммируются до заданного числа.например: 4 -> [1,1,1,1] [1,1,2] [2,2] [1,3]

Я выбираю решение, которое генерирует все возможные подмножества (2 ^n) и затем выведите только те, сумма которых равна числу.У меня проблема с состоянием.Код: 

def allSum(number):
    #mask = [0] * number
    for i in xrange(2**number):
        subSet = []
        for j in xrange(number):
            #if :
                subSet.append(j)
        if sum(subSet) == number:
           yield subSet



for i in allSum(4):
    print i

Кстати, это хороший подход?

Ответы [ 4 ]

4 голосов
/ 30 ноября 2011

Вот код, который я видел несколько лет назад, который делает трюк: 

>>> def partitions(n):
        if n:
            for subpart in partitions(n-1):
                yield [1] + subpart
                if subpart and (len(subpart) < 2 or subpart[1] > subpart[0]):
                    yield [subpart[0] + 1] + subpart[1:]
        else:
            yield []

>>> print list(partitions(4))
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]

Дополнительные ссылки:

1 голос
/ 30 ноября 2011

Это эквивалентно проблеме, описанной в этом вопросе , и может использовать аналогичное решение.

Для уточнения: 

def allSum(number):
    for solution in possibilites(range(1, number+1), number):
        expanded = []
        for value, qty in zip(range(1, number+1), solution):
            expanded.extend([value]*qty)
        yield expanded

Это переводит этот вопрос в этот вопрос и обратно.

1 голос
/ 30 ноября 2011

Вот альтернативный подход, который работает, беря список всех 1 и рекурсивно сворачивая его, добавляя последующие элементы, это должно быть более эффективно, чем генерация всех возможных подмножеств: 

def allSum(number):
    def _collapse(lst):
        yield lst
        while len(lst) > 1:
            lst = lst[:-2] + [lst[-2] + lst[-1]]
            for prefix in _collapse(lst[:-1]):
                if not prefix or prefix[-1] <= lst[-1]:
                    yield prefix + [lst[-1]]
    return list(_collapse([1] * number))

>>> allSum(4)
[[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
>>> allSum(5)
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]

Вы можете удалитьпоследнее значение, если вы не хотите тривиальный случай.Если вы просто просматриваете результаты, удалите вызов list и просто верните генератор.

1 голос
/ 30 ноября 2011

Это решение не работает, верно? Он никогда не добавит число к подмножеству более одного раза, поэтому вы никогда не получите, например, [1,1,2]. Он также никогда не пропустит число, поэтому вы никогда не получите, например, [1,3].

Итак, проблема с вашим решением двоякая: во-первых, вы фактически не генерируете все возможные подмножества в диапазоне 1..number. Во-вторых, набор всех подмножеств исключит то, что вы должны включать, потому что он не позволит номеру появляться более одного раза.

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

...