Алгоритм разбиения?

Question

[Владимир Куц]

Допустим у меня есть кучка неких предметов. Я делю кучку на 2 части. И создаю комбинации в разных вариантах, но так чтобы они не повторялись, в том числе при перемене мест
К примеру у меня в кучке числа 1 2 3 4. Я могу их разбить на две кучки в таких комбинациях:

1   234
2   134
3   124
4   123
12   34
13   24
14   23

21 34 - уже не подходит так как была комбинация 12 34
23 14 - также не подходит так как была уже комбинация 14 23
234 1 - не подходит так как уже было 1 234
и т.п.

Далее нужно это интерпретировать в разбиении на 3, 4, и т.п. кучек возможных уникальных комбинаций деления данных предметов. Очевидно что набор из примера максимум можно разбить на 4 части в единственном варианте
1 2 3 4
Есть какой готовый алгоритм для быстрой генерации данного типа последовательности чтобы тупо не перебирать все варианты и не хранить все промежуточные? Если есть что-то в библиотеках Python - было бы вообще супер.

Comments

[Akina]

Это обычное выделение подмножества из множества. Поскольку надо не получать дубликатов - первый элемент фиксируется в выбираемом подмножестве и не попадает в остаток. Т.е. обычная битовая N-1 задача.

Answer 1

[Wataru]

Алгоритм простой - рекурсивно генерируйте все разбиения.
Текущий предмет может пойти или в одну из занятых кучек, или в первую пустую, если они есть.
Так, первый предмет обязательно пойдет в первую группу. Второй может пойти в ту же или во вторую. И т.д.
Чтобы не было пустых групп, элемент обязательно кладется в первую пустую, если их осталось столько же, сколько осталось элементов распределить. Ну, и, нельзя создавать новую группу, их уже, сколько надо. Удобнее распологать элементы с конца.
Что-то вроде такого:

def partition(n, k, answer):
    if n == 0 :
      yield answer
    cur_len = len(answer)
    if k-cur_len < n:
        for i in range(cur_len):
            answer[i].append(n)
            yield from partition(n-1, k, answer)
            answer[i].pop()
    if cur_len < k:
        answer.append([n])
        yield from partition(n-1,k, answer)
        answer.pop()

for x in partition(4, 2, []):
    print(x)

Вроде как set_partitions из пакета more-itertools делает именно то, что вам надо, но так-то алгоритм - всего несколько строк.

Этот алгоритм переберет все разбиения без повторов, потому что групировка элементов однозначно задает и порядок групп (группа с 1 - всегда первая. Потом группа с минимальным элементом - вторая и т.д.)

Edit:
Если же вам надо разбить предметы по 1, 2 и т.д. групп сразу же, а не только на фиксированные k групп, то надо чуть поменять условия в коде - надо сделать return в начале, после yield, и можно будет ставить предмет в любую группу или в новую всегда. Параметр k будет не нужен.

Comments

[Владимир Куц]

Точно! Супер - почему сразу такое в голову не пришло... )