问题标签 [integer-partition]

我正在尝试将 Python 生成器转换为 C 中的函数。如果值得一提，我正在尝试编写一个程序，将整数 n 划分为 l 个不同的部分。我相信我已经完成了大部分工作，我不知道如何实现产量。这是发电机

这就是我到目前为止所拥有的

我有一个整数 N，我希望随机生成一个可能的分区。例如，N=5 有 7 个分区：

1. (5) - K=1 份
2. (4, 1) - K=2 份
3. (3, 2) - K=2 份
4. (3, 1, 1) - K=3 份
5. (2, 2, 1) - K=3 份
6. (2, 1, 1, 1) - K=4 份
7. (1, 1, 1, 1, 1) - K=5 份

我想要一种算法，它可以以 1/7 的概率输出这些中的每一个。

生成所有此类分区或仅限于 K 个部分的所有分区的算法很容易找到。

但是，我正在寻找的不是先验限制 K。我不能随机均匀地选择 K，因为 K 不是均匀分布的，而且分布不是微不足道的。如果我事先知道零件尺寸的精确分布，我可以使用它对 K 进行采样，然后使用现有算法之一，但我找不到这样做的方法。一项数值调查表明，绝大多数分区的 K 都很小。

我无法预先生成分区列表，因为 N=100 已经有数亿个分区了。但即使对于我需要的范围内的 N=1000，每个单独的分区也将主要是一个小数字的简短列表。

这样的算法存在吗？我找不到它，我已经找了好几天了。

I'm working on a music related problem and I need some help with a crucial step.

I have four lists of numbers from 0 to 11 (including). These lists are to be thought of as vertically aligned. I want to partition those 4 lists into 4 blocks, each block containing all the numbers from 0 to 11, and each row of the block containing 0 to 11 elements from each list. An example:

A solution is to take elements from the beginning of each row and combining then. For example, a solution for partitioning this block is:

The block would look like this:

Here, if we take the elements of same index on each p_list, we have a complete listing of the numbers from 0 to 11 (we can see this by looking at the lists vertically). For instance:

My problem is not to verify a solution, is to actually find one algorhitmically. That is, given 4 rows, how to find a sequence of partitions that is a solution to the problem. Since my background is mostly on music, I come to you for some assistance.

Thank you in advance!

EDIT: As pointed out below, there's also the [(12),(12),(12),(12)] solution. The goal here is to achieve as much diversity as possible of solutions, running this algorhithm through a large number of quartets of different rows.