所有分区都可以在两个阶段找到。
第一个:从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.
的问题是多少?或者你需要找到他们? – 2011-05-08 17:37:53
你的解决方案是什么? – Ishtar 2011-05-08 17:47:02
我的解决方案需要列出分解。我只想列举它们。我生成C的所有排列,然后将所有分解存储在一个表中并计算不同的分解。 – PhilippeC 2011-05-08 21:33:52