Реализация алгоритма «Генерация мощности»

Question

Что такое хорошая реализация алгоритма Power Set?

Недавно мне понадобился этот алгоритм для создания решателя для моей головоломки. Как правило, решатель должен пробовать стратегии (наборы ходов, наборы возможных ходов) и находить стратегию, которая формирует решение.

Я обнаружил, что наивная реализация показана на страница Википедии , а также библиотека из библиотеки js-combinatorics не обеспечивает стабильный порядок элементов в сгенерированных подмножествах.

Кроме того, наивный подход, использующий биекцию набора в набор натуральных чисел и последующее двоичное представление, ограничен размером исходного набора.

Это ограничение естественно возникает из-за того, что внутренне упомянутая библиотека использует 32-битное целочисленное значение для генерации подмножеств.

Answer 1

Используйте реализацию из рецептов itertools :

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

print(*powerset([1,2,3])) 

Вывод:

() (1,) (2,) (3,) (1, 2) (1, 3) (2, 3) (1, 2, 3)

It производит кортежи - но вы можете конвертировать их, как вам нравится. Это выглядит также намного короче, чем ваше решение ...

Answer 2

Вероятно, Stackoverflow - не лучший вариант для обмена фрагментами Gist, но есть связанные вопросы, и я решил поделиться своим фрагментом здесь, с хорошей уверенностью, что он может быть полезен для людей, которые ищут реализацию алгоритма Power Set и для самого сообщества Stackoverflow.

https://gist.github.com/vladignatyev/e76b5fd1c3cdfff7034ce17506fae36e

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

Usage:
    >>> ps = power_set([1,2,3])
    >>> for ss in ps:
            print(ss)
Output:
    [], 
    [1], 
    [2], 
    [3], 
    [1, 2], 
    [1, 3], 
    [2, 3], 
    [1, 2, 3]

Для вашей информации я перенес свой код на чистый Swift 5, никаких зависимостей не требуется. Выезд -> https://gist.github.com/vladignatyev/7e9399930cb614d6251a4f82b8e75ff1