Установить разделы в Python

Ответ 1

Поскольку этот приятный вопрос был возвращен к жизни, вот свежий ответ.

Проблема рекурсивно решается: если у вас уже есть раздел элементов n-1, как вы используете его для разбиения n элементов? Либо поместите n-й элемент в один из существующих подмножеств, либо добавьте его как новое одноэлементное подмножество. Это все, что требуется; no itertools, нет наборов, нет повторных выходов и всего всего n вызовов partition():

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


something = list(range(1,5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))

Вывод:

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

Ответ 2

В отличие от моих комментариев, я не смог быстро найти решение на основе itertools относительно быстро! Изменить: это уже не совсем так, у меня довольно короткое (но медленное и нечитаемое) решение с использованием itertools в значительной степени, см. Конец ответа. Это то, что я получил вместо:

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

например. для списка длины 3 комбинации или разбиения являются (3), (2, 1), (1, 2) и (1, 1, 1). Поэтому мы возвращаем первые 3 элемента списка; первые 2, а затем следующий 1; первый 1, затем следующий 2 и первый 1, затем следующий 1, затем следующий 1.

Я получил код для целочисленного partioning из здесь. Однако функции разделов не возвращают все перестановки разделов (т.е. Для 3 она просто вернет (3), (2, 1) и (1, 1, 1). Поэтому нам нужно вызвать itertools.permutations на каждом из Затем нам нужно удалить дубликаты - так же, как permutations([1, 2, 3]) - [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]; permutations([1, 1, 1]) - [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]. Легкий способ удаления дубликатов - это превратить каждый список кортежей в set.

Тогда все, что остается, - это получение фрагментов списка для длин в кортеже. Например. f([1, 2, 3], [0, 0, 1, 2, 1, 0]) переходит в [[0], [0, 1], [2, 1, 0]].

Мое определение этого:

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

Теперь мы просто объединяем все:

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

>>> for i in subgrups(my_list):
        print(i)

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

Кроме того, вам нужно сделать import itertools и from copy import deepcopy в верхней части программы.

Изменить: ваш данный результат неясен. Я предположил, что вам нужна функция, которую я вам дал, но ваш вывод также содержит [[1,3],[2]], где элементы на выходе находятся в другом порядке, в отличие от остальной части вашего предлагаемого вывода (я взял на себя смелость предположить, что вы на самом деле хотите [[1, 2], [3]] не [[1, 2], 3]).

То есть, я предполагаю, что вы хотели дать в качестве вывода:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

Если на самом деле это было так:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
[[1], [3], [2]]
[[1], [3, 2]]
[[1, 3], [2]]
[[1, 3, 2]]
[[2], [1], [3]]
[[2], [1, 3]]
[[2, 1], [3]]
[[2, 1, 3]]
[[2], [3], [1]]
[[2], [3, 1]]
[[2, 3], [1]]
[[2, 3, 1]]
[[3], [1], [2]]
[[3], [1, 2]]
[[3, 1], [2]]
[[3, 1, 2]]
[[3], [2], [1]]
[[3], [2, 1]]
[[3, 2], [1]]
[[3, 2, 1]]

Затем вам просто нужно вызвать subgrups для каждой трехмерной перестановки исходного списка, например. для каждой перестановки в itertools.permutations(my_list, len(my_list)).

Изменить: Теперь, чтобы выполнить мое обещание короткого решения itertools. Предупреждение - оно может быть как нечитаемым, так и медленным.

Сначала заменим slice_by_lengths следующим образом:

def sbl(lengths, the_list):
    for index, length in enumerate(lengths):
        total_so_far = sum(lengths[:index])
        yield the_list[total_so_far:total_so_far+length]

Затем из this ответ получим нашу целочисленную функцию разбиения:

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

Эта функция фактически получает все перестановки целочисленных разделов для нас, поэтому нам не нужно

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

больше. Тем не менее, он намного медленнее, чем у нас раньше, поскольку он является рекурсивным (и мы реализуем его в Python).

Затем мы просто разделим его:

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

Или менее читаемый, но без определений функций:

def subgrups(my_list):
    for each_tuple in (lambda p, f=lambda n, g:
                          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
                              f(p, f))(len(my_list)):
        yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))

который является определением функции и двумя строками, настолько близкими к тому, что я изначально указывал (хотя и гораздо менее читаемым и гораздо медленнее)!

(Функции, называемые subgrups, потому что первоначально задан вопрос об обнаружении "всех подгрупп" )

Ответ 3

Рассмотрим more_itertools.set_partitions.

Дано

import more_itertools as mit


lst = [1, 2, 3]

Код

Сгладить диапазон из k установленных разделов:

[part for k in range(1, len(lst) + 1) for part in mit.set_partitions(lst, k)]

Выход

 [((1, 2, 3),),
  ((1,), (2, 3)),
  ((2,), (1, 3)),
  ((3,), (1, 2)),
  ((1,), (2,), (3,))]

more_itertools - сторонний пакет. Установить через > pip install more_itertools.