Как перечислить комбинации комбинаций из одного набора

Я понимаю, что есть куча вопросов о комбинаторике и перечислении, но я искал вокруг и не нашел ничего, относящегося конкретно к тому, что я ищу. Если я что-то пропустил, пожалуйста, укажите мне на это, и вопрос может быть закрыт.

Итак, предположим, что у нас есть множество из N элементов, и у нас есть x положительных целых чисел k1,..., kx где Sum (k1,..., kx)

Надеюсь, я правильно выразился. На случай, если нет, приведу простой пример.
N = 4, x = 2, k1 = 2, k2 = 1.

Мы должны перечислить

  • {1, 2} {3}
  • {1, 2} {4}
  • {1, 3} {2}
  • {1, 3} {4}
  • {1, 4} {2}
  • {1, 4} {3}
  • {2, 3} {1}
  • {2, 3} {4}
  • {2, 4} {1}
  • {2, 4} {3}
  • {3, 4} {1}
  • {3, 4} {2}

В общем случае общее количество, я думаю, будет:

C(N, k1) * C(N - k1, k2)*... * C (N-сумма (k1,...,КН-1), кн).

Мое первоначальное предположение состоит в том, что это можно было бы сделать довольно легко, используя стек. На каждом уровне стека I подмножество ki будет генерироваться с использованием стандартного перечисления комбинаций, либо удаляя из исходного набора на каждом уровне те элементы, которые были выбраны, либо просто перечисляя из исходного набора и пропуская случаи, когда элемент был включен ранее.

Мой вопрос: есть ли более быстрое / элегантное решение?

1 2
algorithm combinations recursion combinatorics

1 ответ:

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

Во - первых, заметим, что задача точно эквивалентна задаче, где Σk &равно N, потому что если Σk x+1, значение которого равно N-Σk.

Теперь положите элементы исходного множества s в некоторый произвольный фиксированный порядок, и создать каждой перестановки мультимножества, состоящего из K1 1 это, к2 2 это, к3 3 это, ... k x X. Этот мультисет имеет одинаковый размер (N) S, потому что K i складываются в N. Мы создаем разбиение S, присваивая каждый элемент в S подмножеству, индекс которого является соответствующим значением в перестановке мультисета.

Например, S = {яблоко, банан, чиримоя, финик} (N = 4). Мы берем к1 = 2 и к2 = 1 и добавить k3 = 1 довести сумму до 4. (Мы просто проигнорируем элементы, назначенные подмножеству 3). Теперь перечислим перестановки множества 1 1 2 3 (которое имеет два 1, Один 2 и один 3, соответствующие k): 
1 1 2 3    1 2 3 1    2 1 1 3    3 1 1 2
1 1 3 2    1 3 1 2    2 1 3 1    3 1 2 1
1 2 1 3    1 3 1 1    2 3 1 1    3 2 1 1

Мы преобразуем их обратно в разделы S. например, принимая 1 3 1 2: 

apple     1 -> subset 1
banana    3 -> unused
chirimoya 1 -> subset 1
date      2 -> subset 2

Итак, у нас есть {{apple, chirimoya}, {date}}

Стандартный алгоритмдля нахождения перестановок множества работает так же хорошо на мультисетях, хотя он не является оптимальным, если мультисет имеет много дубликатов.

2