fox_12
@fox_12
Расставляю биты, управляю заряженными частицами

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

Допустим у меня есть кучка неких предметов. Я делю кучку на 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 - было бы вообще супер.
  • Вопрос задан
  • 83 просмотра
Решения вопроса 1
wataru
@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 будет не нужен.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы