Я только что написал небольшую рекурсивную программу для генерации всех возможных подразделений списка:
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}}}
Кроме того, смысл вопроса заключался в том, чтобы выяснить, какова терминология этого; Я называю это «подразделениями»; этот ответ называет это «перегородками». Я ищу хороший ресурс, в котором перечислены все эти шаблоны, чтобы люди не изобретали велосипед заново.
Это другое; существует 24 варианта "abcd", и они не сохраняют порядок. Точно так же комбинации делают что-то другое, когда вы получаете подмножества списка одного размера.
Большое спасибо @EugenePrimako! Разница в том, что это список (упорядоченный), а не набор, и я хочу сохранить порядок. Я предоставил свой собственный ответ из pov программирования, то, что я надеюсь, в ответе - это указатель на некоторые ресурсы, чтобы не изобретать велосипед.
@Prune Я не понимаю, почему этот вопрос Python является дубликатом вопроса Java, который вы предложили?
@pylang: Спасибо за предупреждение; Я вижу разницу. Вопрос открыт повторно.
Спасибо @EugenePrimako, не могли бы вы теперь вставить этот комментарий в ответ ?? И повторить; в этом вопросе есть мета-элемент; Я замечаю, что пишу такие вещи, зная в глубине души, что кто-то уже сделал это, поэтому я ищу, как получить знания о терминологии, такой как «Power set» и «Partition», которых у меня не было. гугл-фу для. Есть ли еще какие-нибудь библиотеки, кроме itertools?
Это могло бы сделать работу немного быстрее (используя 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 - длина последовательности. Хотя не знаю, как называется такая цепочка.
Позвольте мне дать некоторую математическую интерпретацию этой проблемы.
Представьте: у вас есть список 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 Да, я имел в виду "инклюзивный". Обновил свой ответ.
Я предпочитаю ваше второе решение, но оно дает мне ['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)
.
@BasSwinckels Большое спасибо! Это была моя опечатка при рефакторинге кода :( По поводу repeat
- вы правы, сейчас он выглядит намного лучше.
Поиск всех перегородки списка эквивалентен поиску всех наборов индексов, по которым нужно разрезать список.
Например, имея список 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, чтобы найти существующее решение этой проблемы.
Мое решение:
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'
Спасибо. Он также работает в Python 2.7. Но вы правы в том, что передача ему списка не сработает, потому что это решение полагается на использование набора для устранения дубликатов, а последовательность должна быть хешируемой, чтобы быть добавленной в набор, а список - нет. Вы всегда можете преобразовать список в кортеж, прежде чем передать его.
Круто, создание дубликатов с последующим их удалением кажется менее эффективным, чем другие решения.
перестановка возможно.