Подсчет подмножеств с заданными размерами набора

Question

Учитывая набор C с n элементами (допускаются дубликаты) и раздел P с n
P = {i1, i2, ... / i1 + i2 + ... = n} сколько существует разложений C в подмножествах размера i1, i2, ...?

Пример:

C = {2 2 2 3}

P = {2 2}
C = {2 2} U {2 3}

P = {1 1 2}
C = {2} U {2} U {2 3}
C = {2} U {3} U {2 2}

P = {1 3}
C = {2} U {2 2 3}
C = {3} U {2 2 2}

У меня есть решение, но оно неэффективно, когда в С содержится более десятка элементов.
Заранее спасибо
Philippe

Answer 1

Тот факт, что порядок разложения не имеет значения для вас, делает его намного сложнее.То есть вы просматриваете {2 2} U {2 3} так же, как {2 3} U {2 2}.Тем не менее, у меня есть алгоритм, который лучше, чем у вас, но не очень хорош.

Позвольте мне начать его с реально сложного примера.Наш набор будет A B C D E F F F F G G G G.Раздел будет 1 1 1 1 2 2 5.

Мое первое упрощение будет состоять в том, чтобы представить информацию, которая нам нужна в наборе, с помощью структуры данных [[2, 4], [5, 1]], то есть 2 элемента повторяются 4 раза, а 5 повторяются один раз..

Мое второе очевидное осложнение будет состоять в представлении раздела с помощью [[5, 1, 1], [2, 2, 1], [4, 1, 1].Шаблон не может быть очевидным.Каждая запись имеет вид [size, count, frequency].Таким образом, один отдельный экземпляр 2 разделов размера 2 превращается в [2, 2, 1].Мы еще не используем частоту, но она учитывает различимые кучи одинакового размера и общности.

Теперь мы собираемся выполнить следующие действия.Мы возьмем самый распространенный элемент и найдем все способы его использования.Таким образом, в нашем случае мы берем одну из куч размера 4 и находим, что можем разделить ее следующим образом, переставляя каждую оставшуюся стратегию разбиения в лексикографическом порядке:

1. [4], оставляя [[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]].
2. [3, [1, 0], 0] оставляя [[2, 1, 1], [1, 1, 1], [2, 1, 1], [1, 4, 1]] = [[2, 1, 2], [1, 4, 1], [1, 1, 1].(Обратите внимание, что мы сейчас используем частоту.)
3. [3, 0, 1] оставляя [[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]
4. [2, [2, 0], 0] оставляя [[3, 1, 1], [0, 1, 1], [2, 1, 1], [1, 4, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1]]
5. [2, [1, 1], 0] оставляя [[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]
6. [2, [1, 0], [1]] оставляя [[3, 1, 1], [1, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[3, 1, 1], [2, 1, 1], [1, 4, 1], [1, 1, 1]]
7. [2, 0, [1, 1]] оставляя `[[3, 1, 1], [2, 2, 1], [0, 2, 1], [1, 2, 1]] = [[3, 1, 1], [2, 2, 1], [1, 2, 1]] 1
8. [1, [2, 1]], оставляя [[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]
9. [1, [2, 0], [1]] отъезд [[4, 1, 1], [0, 1, 1], [2, 1, 1], [0, 1, 1], [1, 3, 1]] = [[4, 1, 1], [2, 1, 1], [1, 3, 1]]
10. [1, [1, 0], [1, 1]] отъезд [[4, 1, 1], [1, 1, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[4, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 1]]
11. [1, 0, [1, 1, 1]] отъезд [[4, 1, 1], [2, 2, 1], [0, 3, 1], [1, 1, 1]] = [[4, 1, 1], [2, 2, 1], [1, 1, 1]]
12. [0, [2, 2]] отъезд [[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]
13. [0, [2, 1], [1]] отъезд [[5, 1, 1], [0, 1, 1], [1, 1, 1], [0, 1, 1], [1, 3, 1]] = [[5, 1, 1], [1, 3, 1], [1, 1, 1]]
14. [0, [2, 0], [1, 1]] отъезд [[5, 1, 1], [0, 2, 1], [2, 1, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1], [2, 1, 1], [1, 2, 1]]
15. [0, [1, 1], [1, 1]] отъезд [[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]]
16. [0, [1, 0], [1, 1, 1]] отъезд [[5, 1, 1], [1, 1, 1], [2, 1, 1], [0, 3, 1], [1, 1, 1]] = [[5, 1, 1], [2, 1, 1], [1, 1, 2]]
17. [0, 0, [1, 1, 1, 1]] оставляя [[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]

Теперь каждая из этих подзадач может быть решена рекурсивно.Может показаться, что мы находимся на пути к их построению, но это не так, потому что мы запоминаем рекурсивные шаги.Оказывается, есть много способов, которыми первые две группы из 8 могут оказаться с теми же 5 оставшимися кадрами.С пометкой нам не нужно повторно пересчитывать эти решения.

Тем не менее, мы сделаем лучше.Группы из 12 элементов не должны создавать проблем.Но мы не делаем это намного лучше.Я не удивлюсь, если он начнет разбиваться где-то около 30 или около того элементов с интересными наборами разделов.(Я не кодировал его. Это может быть хорошо в 30 и сломаться в 50. Я не знаю, где это сломается. Но учитывая, что вы перебираете наборы разделов, в какой-то довольно небольшой момент это сломается сломается.)

Answer 2

Все разделы можно найти в 2 этапа.

Первый: из P создать новый упорядоченный раздел из n, P_S={P_i1, P_i2, ..., P_ip}, суммируя идентичные i.

P = {1, 1, 1, 1, 2, 2, 5}
P_S = (4, 4, 5)

Создать разделы{C_i1, C_i2, ..., C_ip} из C относительно P_S.Обратите внимание, что C_ix является множественным, как C.Он разбивает C на несколько множеств по размерам конечных разделов.

Секунда: для каждого {C_i1, C_i2, ..., C_ip} и для каждого ix, x={1,2,...,p} найдите количество разделов C_ix в t (число ix's в P) наборы с ix элементами.Позвоните по этому номеру N(C_ix,ix,t).

Общее количество разделов:

sum by all {C_i1, C_i2, ..., C_ip} ( product N(C_ix,ix,t) ix={1,2,...,p} )

Первая часть может быть выполнена рекурсивно довольно просто.Второе сложнее.Разделение множества M на части n с элементами k аналогично нахождению всего частично отсортированного списка с элементами из M.Частично список заказов имеет тип:

a_1_1, a_1_2, ..., a_1_k, a_2_1, a_2_2, ..., a_2_k, ....

Где a_i_x <= a_i_y, если x < y и (a_x_1, a_x_2, ..., a_x_k) lexicographic <= (a_y_1, a_y_2, ..., a_y_k), если x < y.С этими двумя условиями можно рекурсивно создать весь раздел из N(C_ix,ix,t).

В некоторых случаях N(C_ix,ix,t) легко вычислить.Определите |C_ix| как количество различных элементов в множестве C_ix.

if t = 1 than 1
if |C_ix| = 1 than 1
if |C_ix| = 2 than (let m=minimal number of occurrences of elements in C_ix) floor(m/2) + 1
 in general if |C_ix| = 2 than partition of m in numbers <= t.