Generate a series of random numbers that add up to

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

My Original Statement:

You can only generate 29 random numbers. The 30th number will be defined by the other 29 and the sum. This is statistically important...

I wanted to add some clarification after thinking about it and pinging the community...

I now believe my original statement to be false. It was too lenient(which lc pointed out). You can't even generate 29 truly random numbers. As you get closer and closer to 30, the final digits aren't random the same way that rnd[1..9] is random. lc tried to mitigate this in order to come up with a solution, but I believe the solution he came up with (and Spencer) answers a very different question. That question is "Of all the sets of 30 digits between 1 and 9 that add up to 200, construct one randomly".

What I believe to be the case is that the question as stated is unsolvable which I believe can be proved with the Pigeonhole Principle (also used by Knuth to show that certain "random" shuffles weren't really random), but I haven't done the math.

Good talk everyone.

Answer 2

This is an old question but I discovered it looking for a solution to this problem for a practical use in a random data generation testing application.

Based on the ideas in this post I came up with two potential solutions.

The first method:

1. Figure out the lowest integer value that can be repeated to add up to a number near the desired total. Essentially, just do integer division.
2. Initialize an array with all of the values equaling the number found in step 1.
3. If there is a remainder (there usually will be), randomly add one to items in the array and decrement the remainder until the remainder is 0. At this point we have an array which will equal the desired total, but it will be very un-random.
4. For a number of iterations, randomly add and subtract from two locations in the array. Example: add 1 to position 0 and subtract 1 from position 4. In so doing, do bounds checks (all numbers should be at least 0 and all numbers should be no greater than an upper bound).

The second method is much simpler but results in a less random distribution:

1. Initialize an array of 0's of the desired length.
2. Select a random index in the array and add 1. If the value at that index would exceed the upper bound, ignore it and select another index.
3. Repeat step 2 the number of times indicated by the desired total.

Here is the code:

public static int[] getRandomsWithTotalA(int desiredTotal, int desiredNumbers, int upperBound)
{
    Random r = new Random();

    // Is this even a possible feat?
    if (desiredNumbers * upperBound < desiredTotal) throw new ArgumentException("This is not possible!", "desiredTotal");

    // Start by figuring out the closest number we can get to by repeating the initial number.
    int lowestRepeating = desiredTotal / desiredNumbers;

    // Determine the remainder
    int lowestRepeatingRemainder = desiredTotal % desiredNumbers;

    // Initialize and populate an array of numbers with the lowest repeater.
    int[] results = Enumerable.Repeat(lowestRepeating, desiredNumbers).ToArray();

    // We will perform (n*desiredTotal) shuffles.
    int shuffles = (desiredTotal * desiredNumbers);

    while (shuffles > 0)
    {
        int a = r.Next(desiredNumbers);
        int b= r.Next(desiredNumbers);
        if (a==b) continue; // do nothing if they're equal - try again.

        // Test bounds.
        if (results[a]+1>upperBound) continue;
        if (results[b]-1<0) continue;

        // Add one to the first item.
        results[a]++;

        // Do we still have a remainder left? If so, add one but don't subtract from
        // somewhere else.
        if (lowestRepeatingRemainder>0)
        {
            lowestRepeatingRemainder--;
            continue;
        }
        // Otherwise subtract from another place.
        results[b]--;
        // decrement shuffles
        shuffles--;
    }

    return results;
}

public static int[] getRandomsWithTotalB(int desiredTotal, int desiredNumbers, int upperBound)
{
    Random r = new Random();

    // Is this even a possible feat?
    if (desiredNumbers * upperBound < desiredTotal) throw new ArgumentException("This is not possible!", "desiredTotal");

    // Initialize and populate an array of numbers with the lowest repeater.
    int[] results = new int[desiredNumbers];

    while (desiredTotal > 0)
    {
        int a = r.Next(desiredNumbers);

        // Test bounds.
        if (results[a] + 1 > upperBound) continue;

        // Add one to the first item.
        results[a]++;

        desiredTotal--;
    }

    return results;
}

A sample run:

static void Main(string[] args)
{
    foreach (int i in getRandomsWithTotalA(200, 30, 9))
    {
        Console.Write("{0}, ", i);
    }
    Console.WriteLine("\n");
    foreach (int i in getRandomsWithTotalB(200, 30, 9))
    {
        Console.Write("{0}, ", i);
    }
}

3, 8, 7, 5, 9, 9, 8, 9, 9, 6, 8, 7, 4, 8, 7, 7, 8, 9, 2, 7, 9, 5, 8, 1, 4, 5, 4, 8, 9, 7,

6, 8, 5, 7, 6, 9, 9, 8, 5, 4, 4, 6, 7, 7, 8, 4, 9, 6, 6, 5, 8, 9, 9, 6, 6, 8, 7, 4, 7, 7, 

These methods are understandably not as evenly distributed as one would like. It would make sense especially with the second method; if you have a random source that is truly evenly distributed, then your selection of the items to increment should have equal probability across all the possible values. The first one could potentially be a bit better also, but it still suffers from the fact that the random source is also ideally evenly distributed.

I feel like it might be possible to improve at least the first method by introducing some form of bias into the index selection, or possibly a randomization of how much we add and subtract (not always 1), or a randomization of whether we actually do the addition/subtraction or not. Just tweaking the number of iterations seems to change the distribution, but after a while it seems that we start favoring the outer boundaries. (Perhaps it's not possible to get a truly even distribution!)

In any case, there you go...A good place to start at least.

Answer 3

public static List<int> getNumbers(int n)
    {
        Random random = new Random(DateTime.Now.Millisecond);
        List<int> obtainedNumbers = new List<int>(); 
        do
        {
            obtainedNumbers.Add(random.Next(1, 9));
        }
        while (n - obtainedNumbers.Sum() > 0);
        return obtainedNumbers;
    }

JaredPar code likes me but its slow, it's like to throw a coin and hope to get the n value.Nice pieces of codes

Answer 4

In order to have an answer not biased towards smaller numbers (or any other bias), you would ideally generate all possible sets of numbers that add up to N. After you have all the sets, randomly select one of the sets. After you've selected the winning set, you can randomly shake up the order of the numbers within that set, if needed.