Поскольку этот приятный вопрос был возвращен к жизни, вот свежий ответ.
Проблема рекурсивно решается: если у вас уже есть раздел n-1 элементов , как вы используете его для разделения элементов n ? Либо поместите элемент n в один из существующих подмножеств, либо добавьте его как новое одноэлементное подмножество. Это все, что нужно; itertools
:
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's 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]]
: itertools
: itertools
: нет itertools
, нет наборов, нет повторных выходов и всего только n