整数分区的共轭

Question

整数分区的共轭是从n的所有分区的集合中随机选择的，也是一个统一的随机样本？我的结果表明是的，这对于快速生成长度为n的n的随机分区是令人鼓舞的，但我无法解释为什么应该或不应该。顺便说一句，我的结果是基于1.）生成一个特定长度（s）的小n（< 70）的所有分区2.）计算每个分区的方差作为宏观描述符和3。 ）比较整个可行集合（对于长度为n的所有分区）与针对小随机样本（即其长度或者匹配s或者其共轭长度匹配s）的随机生成的分区的整个可行集合（对于长度为n的所有分区）的核密度曲线。随机样本的核密度曲线与整个可行集（即n个匹配s的所有分区）的曲线紧密匹配。这在视觉上说明随机样本（其中大部分是共轭分区）捕获基于n和s的可行集的分区间的方差分布。我无法解释为什么它应该像它似乎那样工作;创造性飞跃的失败。注：产生随机样本的许多其他程序产生明显偏向的样本（即不同形状且高度不重叠的核心密度曲线）。

Answer 1

是的。共轭是一种双射操作，因此每个分区都映射到一个唯一的共轭，然后映射回原始分区。因此，不能通过随机均匀选择分区的共轭而引入任何偏差。

我不认为这有助于您随机生成固定长度的分区 - 但您应该适应Nijenhuis & Wilf的算法来正确执行此操作。这应该不是很难做到，因为可以容易地计算n个分区的数量，并且随机生成算法实际上仅依赖于这个。

Knuth包括关于在TAOCP卷4A的第7.2.4.1节中生成随机分区的练习（47）。这对于一个随机均匀生成固定长度分区的高效算法来说是一个很好的起点。