Все возможные подразделения списка

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

def subdivisions(ls):
    yield [ls]
    if len(ls) > 1:
        for i in range(1, len(ls)):
            for lhs in subdivisions(ls[:i]):
                yield lhs + [ls[i:]]

>>> for x in subdivisions('abcd'): print x
... 
['abcd']
['a', 'bcd']
['ab', 'cd']
['a', 'b', 'cd']
['abc', 'd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

Я грубо форсировал это, и мне потребовалось много времени, чтобы понять. Мне интересно, как это называется, поскольку я уверен, что для этого есть название.

В общем, мне интересно, как изучить этот материал с математической точки зрения и есть ли хорошо известные библиотеки программирования, которые охватывают такие полезные алгоритмы (я знаю https://docs.python.org/3/library/itertools.html)


[Edit] вопрос, который помечен как дубликат - получить все возможные перегородки набора - получает другой ответ.

Ищет { {{1,2,3},{}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}} в то время как правильный ответ для меня (в его терминологии) был бы { {{1,2,3}} , {{1},{2,3}} , {{1,2},{3}} , {{1},{2},{3}}}

Кроме того, смысл вопроса заключался в том, чтобы выяснить, какова терминология этого; Я называю это «подразделениями»; этот ответ называет это «перегородками». Я ищу хороший ресурс, в котором перечислены все эти шаблоны, чтобы люди не изобретали велосипед заново.

перестановка возможно.

Yuriy Kravets 07.07.2018 00:05

Это другое; существует 24 варианта "abcd", и они не сохраняют порядок. Точно так же комбинации делают что-то другое, когда вы получаете подмножества списка одного размера.

EoghanM 07.07.2018 00:11
en.wikipedia.org/wiki/Partition_of_a_set
Eugene Primako 07.07.2018 00:15

Большое спасибо @EugenePrimako! Разница в том, что это список (упорядоченный), а не набор, и я хочу сохранить порядок. Я предоставил свой собственный ответ из pov программирования, то, что я надеюсь, в ответе - это указатель на некоторые ресурсы, чтобы не изобретать велосипед.

EoghanM 07.07.2018 00:22

@Prune Я не понимаю, почему этот вопрос Python является дубликатом вопроса Java, который вы предложили?

pylang 07.07.2018 00:46

@pylang: Спасибо за предупреждение; Я вижу разницу. Вопрос открыт повторно.

Prune 07.07.2018 01:00

Спасибо @EugenePrimako, не могли бы вы теперь вставить этот комментарий в ответ ?? И повторить; в этом вопросе есть мета-элемент; Я замечаю, что пишу такие вещи, зная в глубине души, что кто-то уже сделал это, поэтому я ищу, как получить знания о терминологии, такой как «Power set» и «Partition», которых у меня не было. гугл-фу для. Есть ли еще какие-нибудь библиотеки, кроме itertools?

EoghanM 07.07.2018 01:05

Это могло бы сделать работу немного быстрее (используя itertools): from itertools import chain, combinations; s = 'abcd'; indices = chain(*(combinations(range(1, len(s)), i) for i in range(len(s)))); res = [[s[x:y] for x, y in zip((0,) + i, i + (len(s),))] for i in indices]; print(res). Он в основном рассматривает все комбинации от 0-длины до N-1, где N - длина последовательности. Хотя не знаю, как называется такая цепочка.

a_guest 07.07.2018 01:30
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
7
8
636
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Позвольте мне дать некоторую математическую интерпретацию этой проблемы.

Представьте: у вас есть список abcd. Если вы поместите в него несколько разделителей - например, a|bc|d - вы разделите его на подсписки. Все возможные разделители - это a|b|c|d (их количество - N-1, где N - размер списка). Назовем их (разделители) 1, 2, 3.

Тогда все подразделения вашего списка будут сгенерированы всеми комбинации набора {1, 2, 3}. Их будет 2**3 = 8: каждый элемент может быть в комбинации или нет. (Все эти комбинации называются powerset).

Это может помочь вам перечислить все подразделения без рекурсии: вам просто нужно перебирать двоичные числа от 0b000 до 0b111 включительно (range(0, 2**(N-1))):

from itertools import zip_longest, chain

def yield_possible_splits(string):
    N = len(string)
    for i in range(2 ** (N-1)):
        spaces_bitmask = bin(i).replace('0b', '').rjust(N, '0')
        spaces = [' ' if bit == '1' else '' for bit in spaces_bitmask]
        yield ''.join(chain(*zip_longest(spaces, string, fillvalue='')))

Или эквивалентный вариант с использованием itertools.product вместо бинарных манипуляций:

from itertools import zip_longest, chain, product

def yield_possible_splits(string):
    N = len(string)
    for spaces in product(['', ' '], repeat=N-1):
        yield ''.join(chain(*zip_longest(string, spaces, fillvalue='')))

Применение:

print(list(yield_possible_splits('abcd')))
# ['abcd', 'abc d', 'ab cd', 'ab c d', 'a bcd', 'a bc d', 'a b cd', 'a b c d']

Думаю, это range(0b000, 0b1000)? Мне не хватает шага о том, как использовать двоичное значение каждого разделителя для разделения списка!

EoghanM 07.07.2018 01:12

@EoghanM Да, я имел в виду "инклюзивный". Обновил свой ответ.

Eugene Primako 07.07.2018 01:39

Я предпочитаю ваше второе решение, но оно дает мне ['abcd', 'ab cd', 'a bcd', 'a b cd', ' abcd', ' ab cd', ' a bcd', ' a b cd'] (обратите внимание на пробел перед a и то, что между cd никогда не бывает пробелов). Думаю надо аргументы поменять на zip_longest. Я думаю, что также более ясно использовать аргумент repeat в product, как и в product(['', ' '], repeat=N-1).

Bas Swinckels 07.07.2018 14:55

@BasSwinckels Большое спасибо! Это была моя опечатка при рефакторинге кода :( По поводу repeat - вы правы, сейчас он выглядит намного лучше.

Eugene Primako 07.07.2018 19:59
Ответ принят как подходящий

Поиск всех перегородки списка эквивалентен поиску всех наборов индексов, по которым нужно разрезать список.

Например, имея список l = [1, 2, 3, 4], мы можем представить раздел [[1, 2], [3], [4]] списком индексов [2, 3]. В частности, существует взаимно однозначное соответствие между таким списком индексов и разделами.

Это означает, что, имея список l, мы можем найти powersetrange(1, len(l)) и найти каждый соответствующий раздел.

Код

Это решение использует функцию powerset из рецепты itertools. Использование генераторов более эффективно, чем использование рекурсии.

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partitions(lst):
    for indices in powerset(range(1, len(lst))):
        partition = []
        i = 0
        for j in indices:
            partition.append(lst[i:j])
            i = j
        partition.append(lst[i:])

        yield partition

Пример

print(*partitions([1, 2, 3]))
# [[1, 2, 3]] [[1], [2, 3]] [[1, 2], [3]] [[1], [2], [3]]

Пометка как принятый ответ из-за ссылки на docs.python.org/3/library/itertools.html#itertools-recipes, которую я пропустил при поиске itertools, чтобы найти существующее решение этой проблемы.

EoghanM 13.07.2018 14:36

Мое решение:

from itertools import chain, product
def p(l):
    return {(l,)} | {tuple(chain(*s)) for i in range(1, len(l)) for s in product(p(l[:i]), p(l[i:]))}

p('abcd') возвращает:

{('a', 'bcd'), ('abcd',), ('abc', 'd'), ('ab', 'c', 'd'), ('ab', 'cd'), ('a', 'b', 'cd'), ('a', 'bc', 'd'), ('a', 'b', 'c', 'd')}

Прекрасное лаконичное решение - только Python3? К сожалению, не работает, когда список передается в: >>> p (['a', 'b', 'c', 'd']) TypeError: unhashable type: 'list'

EoghanM 13.07.2018 14:22

Спасибо. Он также работает в Python 2.7. Но вы правы в том, что передача ему списка не сработает, потому что это решение полагается на использование набора для устранения дубликатов, а последовательность должна быть хешируемой, чтобы быть добавленной в набор, а список - нет. Вы всегда можете преобразовать список в кортеж, прежде чем передать его.

blhsing 13.07.2018 14:37

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

EoghanM 20.07.2018 15:03

Другие вопросы по теме