通过谷歌搜索可以找到大量有关将整数n分成m部分的所有可能的分区生成的信息，但我没有找到有关随机生成一个等概率分布的随机分区的任何内容。
我该如何生成一个均匀随机的整数划分？
25
- cdf
9
1也许我漏掉了什么。为什么不只是进行 m 次均匀分割（在剩余的可能切割点上）？你可能能够进行一些优化，但可能并不多。 - Beta
2@Beta 我不是很清楚你在建议什么算法。你能具体说明一下吗？此外，对于我能想到的你的建议的可能解释中，有些似乎可能会导致均匀分布，但其他则不会。 - PeterAllenWebb
1这个问题有些模糊不清。例如，顺序是否重要？是否允许零的存在？ - Aryabhatta
2@Moron 通常情况下，在处理分区时，我们认为顺序不重要且不允许出现零。 - PeterAllenWebb
当n很大且n/m=k，其中k是一个小整数时，您可以使用我刚刚在这里发布的相同技巧--https://dev59.com/91XTa4cB1Zd3GeqP5dQb#29849947。或者您可以查看本文的第7节--http://arxiv.org/pdf/1504.06238v1.pdf。 - faceclean
显示剩余4条评论
7个回答
26
这篇文章的标题有些误导人，随机整数分割默认是无限制的，意味着它可以具有任意大小的许多部分。提出的具体问题是关于将n分成m个部分的分区，这是一种受限制的整数分区类型。
对于生成无限制整数分区，一个非常快速简单的算法由Fristedt提出，见于他1993年发表的论文The Structure of Random Partitions of Large Integer中。算法如下：
- 设置x = exp(-pi/sqrt(6n) )。
- 生成独立的随机变量Z(1), Z(2), ..., Z(n)，其中Z(i)的参数为1-x^i，符合几何分布。
- IF sum i*Z(i) = n，其中总和取自i=1,2,...,n，则STOP。
ELSE，请重复步骤2。
一旦算法停止，那么Z(1)是1的数量，Z(2)是2的数量，以此类推，在随机选择的分区中。接受随机选择的Z集合的概率渐近为1/(94n^3)^(1/4)，这意味着人们期望在接受单个样本前运行该算法O(n^(3/4))次。
我花时间解释这个算法的原因是因为它直接适用于将n分成正好m个部分的问题。首先观察到：
将n分成正好m个部分的分区数等于最大部分为m时n的分区数。
然后我们可以直接应用Fristedt算法，但是不必生成Z(1), Z(2), ..., Z(n)，而只需要生成Z(1), Z(2), ..., Z(m-1), Z(m)+1 (这里的+1确保最大部分正好为m，并且在Z(m)>=1的条件下，1+Z(m)与Z(m)的分布相等)，并将所有其他Z(m+1), Z(m+2), ...都设置为0。然后，在第3步获得目标和后，我们也保证有一个无偏样本。要获得n个部分中的确切m个部分的划分，只需取所生成划分的共轭。
相对于Nijenhuis和Wilf的递归方法，它的优点在于除了存储随机变量Z(1)，Z(2)等之外，没有其他存储要求。此外，x的值可以是0到1之间的任何值，这个算法仍然是无偏的！选择一个好的x值，可以使算法更快，尽管第一步的选择几乎对于无限制的整数划分来说是最优的。
如果n非常大，Fristedt算法太慢（且表格方法不可行），则还有其他选项，但它们稍微复杂一些；请参见我的论文 https://sites.google.com/site/stephendesalvo/home/papers 了解概率分治及其应用的更多信息。
- Stephen DeSalvo
2
@stephen-desalvo，你能否脱口而出一个不错的算法来生成_set_分区？我需要生成大量随机的集合分区，其中集合大小为a）64，b）128。 - Yauhen Yakimenka
2集合划分是组合的一个例子：https://arxiv.org/pdf/1308.3279.pdf
在其中，我们使用Poisson(\lambda_i)代替Geometric，其中\lambda_i = x^i/i!，对于任何x>0，x满足：x*e^x=n最优。
一个极快速的算法，使用PDC确定性后半部分，详见：https://arxiv.org/pdf/1411.6698.pdf第8.7节。 - Stephen DeSalvo
11
这里是一段完成此操作的代码。第一次调用它的时间复杂度为O(n2)，但它会构建一个缓存，使得后续调用的时间复杂度为O(n)。
import random
cache = {}
def count_partitions(n, limit):
if n == 0:
return 1
if (n, limit) in cache:
return cache[n, limit]
x = cache[n, limit] = sum(count_partitions(n-k, k) for k in range(1, min(limit, n) + 1))
return x
def random_partition(n):
a = []
limit = n
total = count_partitions(n, limit)
which = random.randrange(total)
while n:
for k in range(1, min(limit, n) + 1):
count = count_partitions(n-k, k)
if which < count:
break
which -= count
a.append(k)
limit = k
n -= k
return a
因此，令total表示分区数。从0到total-1中随机选择一个数k，并生成第k个分区。
- Jason Orendorff
4
所以count_partitions(n, limit)计算n被分成小于或等于limit的部分的分区数量。好的，我知道你是如何计数的了。然后，假设1到count_partitions(n, n)之间存在一个双射，而且这些数字与n的分区相对应，random_partition会选择其中一个整数并构造相应的分区。当然，这种解决方案不完全回答了问题，而问题要求将n随机分为恰好m个部分。我想我应该在标题中明确这一点。然而，我肯定可以根据这个得出自己需要的结果。 - cdf
哦，对不起。我误读了问题！无论如何，我所做的就是拿一些我已经有的生成所有分区的代码，复制两份，将其中一份变成计数函数，另一份变成第k个分区构造函数。完全相同的方法应该适用于你的问题。 - Jason Orendorff
糟糕！我一直没有标记这个问题为已回答。对此感到抱歉。 - cdf
5
来自组合算法第52页的另一个算法，"将n随机分成k部分"
- 随机选择
{1,2,..,n+k-1}中的一个大小为k-1的子集a1,a2, .. ,ak-1（详见下面 1.，2.） - 令
r1=a1-1；对于j=2..k-1，令rj=aj-aj-1-1；令rk= n+k-1-ak-1 rj(j=1..k) 是n的k个部分的随机划分
要有效地生成集合的随机子集，请参见1. 相关答案和2. 此处。 更新 另一种方法是使用单个介于
[0,1]之间的随机数来均匀生成随机分区（也称为组合），详见IVAN STOJMENOVIC, “ON RANDOM AND ADAPTIVE PARALLEL GENERATION OF COMBINATORIAL OBJECTS”（第5节、第10节）。
- Nikos M.
1
只需要再用C#写一个版本。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication6
{
class Program
{
static Random random = new Random();
static void Main(string[] args)
{
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
PrintPartition(GetUniformPartition(24, 5));
Console.ReadKey();
}
static int[] GetUniformPartition(int input, int parts)
{
if(input<= 0 || parts <= 0)
throw new ArgumentException("invalid input or parts");
if (input < MinUniformPartition(parts))
throw new ArgumentException("input is to small");
int[] partition = new int[parts];
int sum = 0;
for (int i = 0; i < parts-1; i++)
{
int max = input - MinUniformPartition(parts - i - 1) - sum;
partition[i] = random.Next(parts - i, max);
sum += partition[i];
}
partition[parts - 1] = input - sum; // last
return partition;
}
// sum of 1,2,3,4,..,n
static int MinUniformPartition(int n)
{
return n * n - 1;
}
static void PrintPartition(int[] p)
{
for (int i = 0; i < p.Length; i++)
{
Console.Write("{0},", p[i]);
}
Console.WriteLine();
}
}
}
这段代码将会产生以下输出：
5,8,7,2,2,
6,6,7,2,3,
5,7,6,2,4,
6,4,3,2,9,
7,8,4,4,1,
- volody
1
我有一个均匀分布的分区生成器。
其中n := 要分割的整数，r:= 切片数量： 该算法是简单地随机插入分割线的朴素方法的修补版本。当我查看其输出时，我发现这种方法的问题在于放置分割线在同一位置的情况不太可能发生。获取{1,1,1}只有一种方法，而获取{2,4,9}有3!种方法，任何{4,2,9}、{2,4,9}、{9,4,2}等都会导致相同的分区位置排序。通过提供额外的显式重复机会来解决了这个问题。对于每个分割线插入，有一定的概率分割线的位置不是随机的，而是被选为以前选择的值的重复。这样就可以平衡朴素方法的不均匀概率分布。
我已经通过穷举证明了r = 3，n = 2时每个分区的概率完全相等。我没有尝试更高的值进行证明，但半心半意的尝试只发现了有希望的迹象。我还对随机输入进行了测试，发现它对我尝试的每个值都至少大致均匀[但可能完全均匀]。
这是C++11的代码：[输出格式与您期望的不同，它是分隔符的位置而不是它们之间空格的大小。不过转换很容易]
#include <vector>
#include <algorithm>
#include <random>
#include <cassert>
template <typename Parting, typename Seed>
vector<Parting> partitionGen(unsigned nparts, unsigned bandw, Seed seed){//nparts is the number of parts, that is, one greater than the number of dividers listed in the output vector. Bandw is the integer being partitioned.
assert(nparts > 0);
vector<Parting> out(nparts-1);
srand(seed);
unsigned genRange = bandw;
for(auto i=out.begin(); i<out.end(); ++i, ++genRange){
unsigned gen = rand()%genRange;
*i = ((gen<bandw)?
gen:
*(i-(gen-bandw+1)));
}
sort(out.begin(), out.end(), less<Parting>());
return out;
}
我不喜欢必须自己排序的事实。如果Vlody的版本有均匀分布，那似乎会更好。
- mako
0
在一些谷歌搜索之后，我在“应用算法手册”中找到了一个针对此问题的算法，其已被谷歌图书索引。该算法出现在第1.12.2节第31页。
- PeterAllenWebb
1
是的，我也遇到了这个问题。它不能生成恰好包含m个部分的分区，并且假定RP(n,m)（相当于Jason的count_partitions(n, limit)，其中limit = m）已经被计算出来了。我认为计算n个部分的m个分区的数量需要做更少的工作。 - cdf
0
我已经实现了上面的解决方案，并发现如果想要计算n的整数分区，它非常有效，但不考虑m。如果处理较大的n，可能需要大幅增加递归限制和调用堆栈。
然而，你不需要第一个函数，因为count_partitions(n, limit)事实上等于' n+limit '中' limit '部分分区的数量。一些数学软件有非常快速的函数来查找将n分成m份的分区数。
最近我衍生出了一种绝对不偏见，非常简单且非常快速（使用记忆化）的方法来解决您的确切问题：在Python中随机生成特定长度的整数分割的算法？
它基于了解具有m个部分的n的字典顺序分区的某些内容，并使用类似于广泛接受的算法（例如Nijenhuis和Wilf 1978）查找n的随机分区的方法，并且在概念上类似于上面的方法。
简而言之，如果有x个由m个部分组成的n的划分，则我们选择一个1到x之间的随机数。该随机数将编码为仅满足n和m的一个划分。希望这可以帮到你。- klocey
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接