c# - 如何加速计算多个项目的所有可能分布的算法？

Question

我想计算一些项目的所有可能(使用特定步骤)分布。总和必须加起来为 1。 我的第一种方法如下:

var percentages = new List<double>(new double[3]);

while (Math.Abs(percentages.Last() - 1.0) > 0.01) 
{
    Increment(percentages, 0);
    if (Math.Abs(percentages.Sum() - 1.0) < 0.01)
    {
        percentages.ForEach(x => Console.Write("{0}\t", x));
        Console.WriteLine();
    }
}

private void Increment(List<double> list, int i)
{
    if (list.Count > i)
    {
        list[i] += 0.1;
        if (list[i] >= 1)
        {
            list[i] = 0;
            Increment(list, ++i);
        }
    }
}

输出想要的结果:

1 0 0
0.9 0.1 0
0.8 0.2 0
0.7 0.3 0
0.6 0.4 0
0.5 0.5 0
0.4 0.6 0
0.3 0.7 0
0.2 0.8 0
0.1 0.9 0
0 1 0
0.9 0 0.1 ..

我想知道如何加快计算速度，因为项目的数量可能会变得非常大 (>20)。 显然我计算了很多分布只是为了把它们扔掉，因为它们加起来不等于 1。 有什么想法吗？

Answer 1

这适用于 3 组数字:

var query =
    from x in Enumerable.Range(0, 11)
    from y in Enumerable.Range(0, 11 - x)
    let z = 10 - x - y
    select new [] { x / 10.0, y / 10.0, z / 10.0 };

var percentages = query.ToList();

percentages
    .ForEach(ps => Console.WriteLine(String.Join("\t", ps)));

---

这是一个通用版本:

Func<int, int[], int[][]> generate = null;
generate = (n, ns) =>
    n == 1
        ? new int[][]
            {
                ns
                    .Concat(new [] { 10 - ns.Sum() })
                    .ToArray()
            }
        : Enumerable
            .Range(0, 11 - ns.Sum())
            .Select(x =>
                ns.Concat(new [] { x }).ToArray())
            .SelectMany(xs => generate(n - 1, xs))
            .ToArray();

var elements = 4;

var percentages =
    generate(elements, new int[] { })
        .Select(xs => xs.Select(x => x / 10.0).ToArray())
        .ToList();

只需更改 elements 值即可获取内部数组的元素数。