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

Учитывая множество 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}

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

Ответы

Ответ 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 и обнаруживаем, что мы можем разделить ее следующим образом, переставляя каждую оставшуюся стратегию раздела в лексикографическом порядке:

  • [4], оставляя [[1, 1, 1], [2, 2, 1], [1, 4, 1]] = [[2, 2, 1], [1, 4, 1], [1, 1, 1]].
  • [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, 0, 1] оставить [[2, 1, 1], [2, 2, 1], [0, 1, 1], [1, 3, 1]] = [[2, 2, 1], [2, 1, 1], [1, 3, 1]]
  • [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]]
  • [2, [1, 1], 0] оставить [[3, 1, 1], [1, 2, 1], [1, 4, 1]] = [[3, 1, 1], [1, 4, 1], [1, 2, 1]]
  • [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]]
  • [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
  • [1, [2, 1]] оставить [[4, 1, 1], [0, 1, 1], [1, 1, 1], [1, 4, 1]] = [[4, 1, 1], [1, 4, 1], [1, 1, 1]]
  • [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]]
  • [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]]
  • [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]]
  • [0, [2, 2]] оставить [[5, 1, 1], [0, 2, 1], [1, 4, 1]] = [[5, 1, 1], [1, 4, 1]]
  • [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]]
  • [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]]
  • [0, [1, 1], [1, 1]] оставить [[5, 1, 1], [1, 2, 1], [0, 2, 1], [1, 2, 1]] = [[5, 1, 1,], [1, 2, 2]]
  • [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]]
  • [0, 0, [1, 1, 1, 1]] оставить [[5, 1, 1], [2, 2, 1], [0, 4, 1]] = [[5, 1, 1], [2, 2, 1]]

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

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

Ответ 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} of 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.