Управление набором мощности в Python

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

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

l = list(powerset(["A", "B"]))
print(l)

который дает:

[[], ['A'], ['B'], ['A', 'B']]

Теперь, как можно взять приведенный выше список, исключить пустой список и объединить последний элемент, чтобы он стал:

['A', 'B', 'AB']

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


python-3.x python list for-loop powerset
person Community    schedule 05.04.2018    source источник
comment
Сначала списки, теперь наборы....почему? Другой ваш вопрос   -  person Patrick Artner    schedule 05.04.2018
comment
Существует itertools - рецепты для powersets: docs.python.org/3.6 /library/itertools.html#itertools-recipes, которые можно изменить, чтобы исключить пустой набор. а также stackoverflow.com/questions/18035595/   -  person Patrick Artner    schedule 05.04.2018
comment
.. установить (он же: список)? Set и list в питоне разные.   -  person Austin    schedule 05.04.2018
comment
@PatrickArtner Спасибо, Патрик, действительно, мне нужно было различать два   -  person    schedule 05.04.2018

Ответы (4)


arrow_upward
1
arrow_downward

Чтобы избавиться от пустого набора, просто начните свой цикл с 1 вместо 0, затем ''.join:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1, 1 << x):
        yield ''.join(ss for mask, ss in zip(masks, s) if i & mask)

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

lst = ["A", "B"]
for _ in range(5):
    lst = list(powerset(lst))
    print(lst)

Сказав это, может иметь смысл выполнять эту фильтрацию и объединение в качестве этапа постобработки, как в ответе @ L3viathan, поскольку истинная функция powerset не должна ни пропускать, ни изменять результаты.

person tobias_k    schedule 05.04.2018

arrow_upward
1
arrow_downward

Сначала отфильтруйте ложные (пустые) элементы, затем соедините элементы оставшихся элементов:

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> list(map(''.join, filter(bool, l)))
['A', 'B', 'AB']

Эквивалентный способ понимания списка:

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> [''.join(e) for e in l if e]
['A', 'B', 'AB']

Чтобы сделать это пять раз, сделайте это пять раз:

start = ["A", "B"]
for _ in range(5):
    start = [''.join(e) for e in powerset(start) if e]
person L3viathan    schedule 05.04.2018
comment
Спасибо, как я могу взять последний список, означающий ['A', 'B', 'AB'], и проделать с ним ту же процедуру сейчас? Я хочу знать, как сделать цикл for внутри. Итак, теперь, когда у меня есть ['A', 'B', 'AB'], у меня может быть 8 подсписков, и я хочу сделать то же самое, что и раньше, а именно удалить пустой список и объединить те, которые находятся в одном подсписке. - person ; 05.04.2018
comment
@tobias_k Мы начинаем с набора [A, B], мы пишем подмножество после исключения пустого подмножества и объединения элементов, поэтому [[], ['A'], ['B'], ['A', ' B']] становится ['A', 'B', 'AB']. Теперь я хочу взять ['A', 'B', 'AB'] и записать его подмножества аналогичным образом. И повторить процедуру 5 раз - person ; 05.04.2018
comment
@William Добавлено, как это повторить. - person L3viathan; 05.04.2018

arrow_upward
0
arrow_downward

Может быть, вам нужно что-то вроде flatmap?

from itertools import chain, imap

def flatmap(f, items):
        return chain.from_iterable(imap(f, items))

>>> list(flatmap(lambda x: x, [[], ['A'], ['B'], ['A', 'B']]))
['A', 'B', 'A', 'B']
person Alper    schedule 05.04.2018

arrow_upward
0
arrow_downward

Это то, что вы искали:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        item = ''.join([ss for mask, ss in zip(masks, s) if i & mask])
        if item:
            yield item
l = list(powerset(["A", "B", "C"]))
print(l) 
#['A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

Я представил C, так как он, очевидно, работает с A и B.

person zipa    schedule 05.04.2018
comment
Спасибо, как я могу взять последний список, означающий ['A', 'B', 'AB'], и проделать с ним ту же процедуру сейчас? Я хочу знать, как сделать цикл for внутри. Итак, теперь, когда у меня есть ['A', 'B', 'AB'], у меня может быть 8 подсписков, и я хочу сделать то же самое, что и раньше, а именно удалить пустой список и объединить те, которые находятся в одном подсписке. - person ; 05.04.2018