如何加快该算法，该算法计算多个项目的所有可能分布

本文关键字：算法 有可能 项目 分布 何加快 计算 | 更新日期: 2023-09-27 18:28:31

我想计算许多项的所有可能的（使用特定步骤）分布。总和必须加起来为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。有什么想法吗？

如何加快该算法，该算法计算多个项目的所有可能分布

这适用于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值即可获得内部数组的元素数。

冒着重复工作的风险，这里有一个与其他答案基本相同的版本。然而，我已经写了，所以我不妨分享一下。我还将指出一些对OP可能重要也可能不重要的差异：

static void Main(string[] args)
{
    Permute(1, 0.1m, new decimal[3], 0);
}
static void Permute(decimal maxValue, decimal increment, decimal[] values, int currentValueIndex)
{
    if (currentValueIndex == values.Length - 1)
    {
        values[currentValueIndex] = maxValue;
        Console.WriteLine(string.Join(", ", values));
        return;
    }
    values[currentValueIndex] = 0;
    while (values[currentValueIndex] <= maxValue)
    {
        Permute(maxValue - values[currentValueIndex], increment, values, currentValueIndex + 1);
        values[currentValueIndex] += increment;
    }
}

注：

  • 我在这里使用decimal类型。在这种特殊情况下，它避免了像原始代码中那样需要基于epsilon的检查
  • 我也更喜欢使用string.Join()，而不是向Console.Write()发出多个调用
  • 同样在这种情况下，List<T>的使用似乎没有好处，所以我的实现使用了一个数组

但我承认，它的基本算法是一样的。

我会把它翻过来。跟踪余数，只递增直到余数。您还可以通过将最后一个元素设置为唯一有效的值来加快速度。这样，你看到的每一个组合都将是可打印的。

如果你用这种方式组织事情，那么你可能会发现把print放在递归函数中是件好事。

我没有用C#编程，但它可能看起来像这样：

var percentages = new List<double>(new double[3]);
PrintCombinations(percentages, 0, 1.0);
private void PrintCombinations(List <double> list, int i, double r) {
    double x = 0.0;
    if (list.Count > i + 1) {
        while (x < r + 0.01) {
            list[i] = x;
            PrintCombinations(list, i+1, r-x);
        }
    }
    else {
        list[i] = r;
        percentages.ForEach(x => Console.Write("{0}'t", x));
        Console.WriteLine();
    }
}

（诚然，这确实把组合放在了一个不同的顺序。修复这个问题只是一个练习…）

如果你所说的"分布"是指"0.1到1.0的3个数字的总和"，那么这个相当直接的方法怎么样：

for (decimal i = 0; i< 1; i+=0.1m)
    for (decimal j = 0; j < 1 - i; j+=0.1m)
    {
        Console.WriteLine(i + " " + j  + " " + (1 - i - j)  );
    }
相关文章：