Generate a series of random numbers that add up to N in c#

Question

How do I generate 30 random numbers between 1-9, that all add up to 200 (or some arbitrary N), in C#?

I'm trying to generate a string of digits that can add together to be N.

Answer 1

I'm not sure what the statistics are on this but, the issue here is that you don't want to randomly select a number that makes it impossible to sum N with M number of entries either by overshooting or undershooting. Here's how I would do it:

static void Main()
{
    int count = 30;
    int[] numbers = getNumbers(count, 155);
    for (int index = 0; index < count; index++)
    {
        Console.Write(numbers[index]);
        if ((index + 1) % 10 == 0)
            Console.WriteLine("");
        else if (index != count - 1)
            Console.Write(",");
    }
    Console.ReadKey();
}
static int[] getNumbers(int count, int total)
{
    const int LOWERBOUND = 1;
    const int UPPERBOUND = 9;

    int[] result = new int[count];
    int currentsum = 0;
    int low, high, calc;

    if((UPPERBOUND * count) < total ||
        (LOWERBOUND * count) > total ||
        UPPERBOUND < LOWERBOUND)
        throw new Exception("Not possible.");

    Random rnd = new Random();

    for (int index = 0; index < count; index++)
    {
        calc = (total - currentsum) - (UPPERBOUND * (count - 1 - index));
        low = calc < LOWERBOUND ? LOWERBOUND : calc;
        calc = (total - currentsum) - (LOWERBOUND * (count - 1 - index));
        high = calc > UPPERBOUND ? UPPERBOUND : calc;

        result[index] = rnd.Next(low, high + 1);

        currentsum += result[index];
    }

    // The tail numbers will tend to drift higher or lower so we should shuffle to compensate somewhat.

    int shuffleCount = rnd.Next(count * 5, count * 10);
    while (shuffleCount-- > 0)
        swap(ref result[rnd.Next(0, count)], ref result[rnd.Next(0, count)]);

    return result;
}
public static void swap(ref int item1, ref int item2)
{
    int temp = item1;
    item1 = item2;
    item2 = temp;
}

I didn't have a lot of time to test this so apologies if there's a flaw in my logic somewhere.

EDIT:

I did some testing and everything seems solid. If you want a nice pretty spread it looks like you want something along the lines of Total = Count * ((UPPER + LOWER) / 2). Although I'm fairly certain that as the difference between UPPER and LOWER increases the more flexible this becomes.

Answer 2

The problem is we want all numbers to be bounded 1-9 and add up to N. So we have to generate each number one by one and determine the real bounds for the next number.

This will of course generate statistical bias toward the end of the list, so I recommend shuffling the array once after generating.

To determine the next number's bounds, do the following: Upper bound = take the remaining sum minus (the number of elements remaining * min). Lower bound = take the remaining sum minus (the number of elements remaining * max).

Something like (untested):

public static List<int> RandomList(int digitMin, int digitMax, 
                                   int targetSum, int numDigits)
{
    List<int> ret = new List<int>(numDigits);

    Random random = new Random();
    int localMin, localMax, nextDigit;
    int remainingSum = targetSum;

    for(int i=1; i<=numDigits; i++)
    {
          localMax = remainingSum - ((numDigits - i) * min);
          if(localMax > max)
              localMax = max;

          localMin = remainingSum - ((length - i) * max);
          if(localMin > min)
              localMin = min;

          nextDigit = random.Next(localMin, localMax);
          ret.Add(nextDigit);
          remainingSum -= nextDigit;
    }

    return ret;
}

The idea here is as you generate numbers, the range of possible values for the remaining numbers gets smaller, like a limit function zeroing in on a target sum. Sort of.

Edit: I had to change the for loop to be 1-based, because we want the number of elements left AFTER generating this one.

Edit2: Put it in a method for completeness and changed length to be numDigits for readability.