計算具有給定尺寸的集合的子集

Question

給定具有n個元素（允許重複）的集合C和n的分區P
P = {i1，i2，...，i1 + i2 + ... = n} 對於大小爲i1，i2，...的子集，C有多少種不同的分解？

實施例：

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具有比元素的十幾。
在此先感謝
菲利普

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 ，1,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]]

現在每個子問題的那些可以遞歸解決。這可能覺得我們正在構建它們的所有方式，但我們不是，因爲我們memoize的遞歸步驟。事實證明，前面兩組8人可以用相同的5個剩餘部分結束。通過記錄我們不需要重複計算這些解決方案。

這就是說，我們會做得更好。 12個元素組不應該成爲問題。但我們沒有做那好多了。如果它開始打破圍繞30個左右分組的有趣的分區組的某個地方，我不會感到驚訝。 （我沒有編碼，在30點可能會好，在50點也可以，但我不知道它會在哪裏崩潰，但是考慮到你正在迭代多組分區，在一些相當小的點上它會變成將分解。）

Answer 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{C_i1, C_i2, ..., C_ip}相對於P_S。請注意，C_ix是多套的，如C。它按照最終分區的大小將C分區成多集。

二：對於每個{C_i1, C_i2, ..., C_ip}和每個ix, x={1,2,...,p}查找數的C_ix分區成t（在P數目的ix's）設置與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}) 

第一部分可以完成遞歸很簡單。其次更復雜。與k元件多設置M成n份的分區相同發現與來自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.