How to speed up this algorithm that calculates all possible distributions of a number of items?

Question

I want to calculate all possible (using a certain step) distributions of a number of items. The sum has to add up to 1. My first approach was the following:

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);
        }
    }
}

Which outputs the wanted results:

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 ..

I'm wondering how to speed up the calculation, as the number of items can become very large (>20). Obviously I calculate a lot of distributions just to throw them away because they don't add up to 1. Any ideas?

Answer 1

This works nicely for 3 sets of numbers:

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)));

---

Here's a generalized version:

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();

Just change the elements value to get the number of elements for the inner array.

Answer 2

I would turn this inside out. Keep track of the remainder, and only increment up until that remainder. You can also speed things up by setting the last element to the only value that can work. That way every combination that you look at is going to be printable.

If you organize things this way, then you will probably find it good to put the print inside the recursive function.

I don't program in C#, but it might look something like this:

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();
    }
}

(Admittedly this does put the combinations in a different order. Fixing that is left as an exercise...)

Answer 3

If by 'distribution' you mean 'sum of 3 numbers in steps of 0.1 adding up to 1.0', how about this rather direct approach:

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)  );
    }

Answer 4

At the risk of duplicating effort, here is a version that is fundamentally the same as the other answer. However, I already wrote it so I might as well share it. I'll also point out some differences that may or may not be important to the 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;
    }
}

Notes:

• I use the decimal type here. In this particular case, it avoids the need for epsilon-based checks as in the original code.
• I prefer also using string.Join() rather than issuing multiple calls to Console.Write().
• Also in this case the use of List<T> doesn't seem beneficial, so my implementation uses an array.

But I admit, its basic algorithm is the same.