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

This program will attempt to give you the answer. But because you are dealing with random numbers, there is the possibility that this will never give you the answer.

public static IEnumerable<int> GetRandom()
{
    var rand = new Random();
    while (true)
    {
        yield return
        rand.Next(1, 9);
    }
}

public static List<int> GetThirtyThatAddToTwoHundred()
{
    do
    {
        var current = GetRandom().Take(30);
        if (200 == current.Sum())
        {
            return current.ToList();
        }
    } while (true);
}

Answer 2

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 3

If statistical bias from true randomness is acceptable, you can add numbers up to N - [max random number], then select the last number as N - sum(selected so far).

Answer 4

Algorithm:

1. Set total = 200 (or whatever)
2. Generate Random number between 1-9
3. Check if (total - newRandomNumber >= 0), if no goto 6
4. total -= newRandomNumber
5. Add newRandomNumber to array, goto 2.
6. newRandomNumber = total
7. Add newRandomNumber to array if newRandomNumber != 0
8. End

Answer 5

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.

Answer 6

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 7

This method will return 30 random numbers that add up to an arbitraryN. It is possible do, to have some 0 values. if that is not feasible, just initialize the array all to one's and if the sum is greater to the arbitraryN, set vals[nextIdx] to 1 instead of 0. Hope this helps.

    private int[] getNumbers(int arbitraryN) {
        int[] vals = new int[30];
        int nextIdx = 0;
        int nextNumber=0;
        Random r = new Random();
        if (arbitraryN > 270 || arbitraryN < 30)
            throw new Exception("Not a Valid number");
        while (vals.Sum() < arbitraryN)
        {
            nextNumber = r.Next(1, 9);
            nextIdx = r.Next(29);
            vals[nextIdx] = nextNumber;
            if (vals.Sum() > arbitraryN)
            {
                vals[nextIdx] = 0;
                vals[nextIdx] = 270 - vals.Sum();
                break;
            }
        }
        return vals;
    }

Answer 8

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 9

There is no guarrentee that 30 random numbers from 1-9 would add up to any specific N.

What you can find is a list of numbers which will add up to N and are bounded from 1-9 but the number will not be 30 necessarily. I believe the minimum number of numbers you need is 23, being (22*9) + 2. The maximum of course will be 200 (200*1). So the length of the list is somewhere inside [23,200]. The chances that a random list may be length 30 is thus quite low. If all list lengths are obtainable (i think they are) your chances in the long run at about 0.5%.

Answer 10

I think this is the simplest way to do it, so it may lack some sophistication however it will get you there.

        String output = "";
        int sum = 0;
        int result = 200;       //enter the "end number"

        Random r = new Random();

        while (sum != result) {
            int add;
            if ((result - sum) > 10)
            {
                add = r.Next(1, 10);
            }
            else
            {
                add = r.Next(result - sum + 1);
            }

            sum += add;
            output += add.ToString() + " + ";
        }

        output = output.Remove(output.Length - 2);

        Console.WriteLine(output);

Hope it helps!

Answer 11

If you want an unbiased algorithm then the naive implementation is something like:

while (true) {
  numbers = [];
  total = 0;
  for (i = 0; i < COUNT; ++i) {
    next = rand(BOUNDS);
    total += next;
    numbers.push(next);
  }

  if (total == TARGET) {
    return numbers;
  }
}

This is non-terminating and slow but it is not biased. If you want a unbiased algorithm I'm not convinced the algorithms posted here are unbiased.

Answer 12

After all the discussions here, there's one other way to generate a list that doesn't introduce bias. Yes, it does differ from what the question is asking, but instead of randomly choosing digits, you can randomly increment digits until you reach the sum. Like the following (again untested):

public static List<int> RandomListByIncrementing(int digitMin, int digitMax, 
                                                 int targetSum, int numDigits)
{
    if(targetSum < digitMin * numDigits || targetSum > digitMax * numDigits)
        throw new ArgumentException("Impossible!", "targetSum");

    List<int> ret = new List<int>(Enumerable.Repeat(digitMin, numDigits));
    List<int> indexList = new List<int>(Enumerable.Range(0, numDigits-1));

    Random random = new Random();
    int index;

    for(int currentSum=numDigits * digitMin; currentSum<targetSum; currentSum++)
    {
        //choose a random digit in the list to increase by 1
        index = random.Next(0,indexList.Length-1);

        if(++ret[indexList[index]] == digitMax)
        {
            //if you've increased it up to the max, remove its reference
            //because you can't increase it anymore
            indexList.RemoveAt(index);
        }
    }

    return ret;
}

The idea here is you keep a list of references to your number list. Choose a reference at random, and increment the corresponding number. If you can't increment it anymore, remove the reference so you don't choose it next time.

Now there's no shuffling business to be done at the end of the day, although arguably this will still produce one of the available sets of answers to the question and it's a question of which one "feels better" or is faster to run.

Answer 13

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.

Answer 14

I thought I'd try a divide and conquer approach. It seems to work pretty well. I'm sure the results aren't truly random due to the constraining elements of the algorithm, but it comes close. Essentially, I split the list in two and the target sum in half and recurse until I get lists of 3 elements or less. Then I use a brute force iteration of random digits until these smaller sums are attained. Here's the code with a sample run below it.

using System;
using System.Collections.Generic;

namespace AddUpClient {
    class Program {

        static void Main() {
            AddUpWorker worker = new AddUpWorker();
            int MinDigit = 1;
            int MaxDigit = 9;
            int ItemsToSum = 30;
            int TargetSum = 150;

            try {
                //Attempt to get a list of pseudo-random list of integers that add up to the target sum
                IList<int> Results = worker.AddUp(MinDigit, MaxDigit, ItemsToSum, TargetSum);

                EvaluateResults(TargetSum, Results);
                Console.ReadLine();
            }
            catch (Exception E) {
                Console.Out.WriteLine("Error: {0}", E.Message);
                return;
            }

        }

        private static void EvaluateResults(int TargetSum, IList<int> Results)
        {
            Console.Out.WriteLine("Results have {0} items.", Results.Count);

            int Sum = 0;
            foreach (int Result in Results) {
                Sum += Result;
                Console.Out.WriteLine("Result: {0} Running total: {1}", Result, Sum);
            }
            Console.Out.WriteLine();
            Console.Out.WriteLine("Result = {0}", (Sum == TargetSum ? "SUCCESS" : "FAIL"));
        }
    }

    internal class AddUpWorker {

        Random RGenerator = new Random();

        public IList<int> AddUp(int MinDigit, int MaxDigit, int ItemsToSum, int TargetSum) {

            Console.Out.WriteLine("AddUp called to sum {0} items to get {1}", ItemsToSum, TargetSum);
            if (ItemsToSum > 3) {

                int LeftItemsToSum = ItemsToSum/2;
                int RightItemsToSum = ItemsToSum - LeftItemsToSum;

                int LeftTargetSum = TargetSum/2;
                int RightTargetSum = TargetSum - LeftTargetSum;


                IList<int> LeftList = AddUp(MinDigit, MaxDigit, LeftItemsToSum, LeftTargetSum);
                IList<int> RightList = AddUp(MinDigit, MaxDigit, RightItemsToSum, RightTargetSum);

                List<int> Results = new List<int>();
                Results.AddRange(LeftList);
                Results.AddRange(RightList);
                return Results;
            }

            // 3 or less

            int MinSumWeCanAchieve = ItemsToSum*MinDigit;
            int MaxSumWeCanAchieve = ItemsToSum*MaxDigit;


            if (TargetSum < MinSumWeCanAchieve)
                throw new ApplicationException("We added up too fast");

            if (TargetSum > MaxSumWeCanAchieve)
                throw new ApplicationException("We added up too slow");

            //Now we know we can achieve the result -- but it may not be too efficient...

            int[] TrialNumbers = new int[ItemsToSum];
            int MaxIteration = 100000;
            int IterationPrintInterval = 1000;
            int TrialSum;
            bool PrintIteration;

            for (int Iteration = 1; Iteration <= MaxIteration; ++Iteration) {

                PrintIteration = ((Iteration % IterationPrintInterval) == 0);

                if (PrintIteration)
                    Console.Out.WriteLine("Iteration {0} attempting to sum {1} numbers to {2}",
                        Iteration, ItemsToSum, TargetSum);

                TrialSum = 0;
                for (int j=0; j < ItemsToSum; ++j) {
                    TrialNumbers[j] = RGenerator.Next(MinDigit, MaxDigit + 1);
                    TrialSum += TrialNumbers[j];
                }
                if (PrintIteration)
                    ShowArray(string.Format("Iteration: {0}", Iteration), TrialNumbers);

                if (TrialSum == TargetSum) {    //Yay
                    ShowArray(string.Format("Success in {0} iterations: ", Iteration), TrialNumbers);
                    return new List<int>(TrialNumbers);
                }
                //try again....
            }

            throw new ApplicationException(string.Format("Maximum of {0} trials exceeded", MaxIteration));
        }

        private void ShowArray(string Prefix, int[] numbers)
        {
            for (int i = 0; i < numbers.Length; ++i) {
                if (i == 0)
                    Console.Write("{0} {1}", Prefix, numbers[i]);
                else
                    Console.Write(", {0}", numbers[i]);
            }
            Console.WriteLine();
        }
    }
}

AddUp called to sum 30 items to get 150
AddUp called to sum 15 items to get 75
AddUp called to sum 7 items to get 37
AddUp called to sum 3 items to get 18
Success in 10 iterations:  7, 2, 9
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 12 iterations:  5, 4
AddUp called to sum 2 items to get 10
Success in 2 iterations:  1, 9
AddUp called to sum 8 items to get 38
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 11 iterations:  4, 5
AddUp called to sum 2 items to get 10
Success in 6 iterations:  8, 2
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 3 iterations:  8, 1
AddUp called to sum 2 items to get 10
Success in 1 iterations:  4, 6
AddUp called to sum 15 items to get 75
AddUp called to sum 7 items to get 37
AddUp called to sum 3 items to get 18
Success in 3 iterations:  4, 6, 8
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 17 iterations:  3, 6
AddUp called to sum 2 items to get 10
Success in 24 iterations:  1, 9
AddUp called to sum 8 items to get 38
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 3 iterations:  2, 7
AddUp called to sum 2 items to get 10
Success in 3 iterations:  1, 9
AddUp called to sum 4 items to get 19
AddUp called to sum 2 items to get 9
Success in 4 iterations:  5, 4
AddUp called to sum 2 items to get 10
Success in 2 iterations:  9, 1
Results have 30 items.
Result: 7 Running total: 7
Result: 2 Running total: 9
Result: 9 Running total: 18
Result: 5 Running total: 23
Result: 4 Running total: 27
Result: 1 Running total: 28
Result: 9 Running total: 37
Result: 4 Running total: 41
Result: 5 Running total: 46
Result: 8 Running total: 54
Result: 2 Running total: 56
Result: 8 Running total: 64
Result: 1 Running total: 65
Result: 4 Running total: 69
Result: 6 Running total: 75
Result: 4 Running total: 79
Result: 6 Running total: 85
Result: 8 Running total: 93
Result: 3 Running total: 96
Result: 6 Running total: 102
Result: 1 Running total: 103
Result: 9 Running total: 112
Result: 2 Running total: 114
Result: 7 Running total: 121
Result: 1 Running total: 122
Result: 9 Running total: 131
Result: 5 Running total: 136
Result: 4 Running total: 140
Result: 9 Running total: 149
Result: 1 Running total: 150

Result = SUCCESS

Answer 15

Backtracking?

Answer 16

So I have to ask: Is there an actual purpose for this, or is it just an exercise or homework assignment? There is a lot of work going on to prevent "bias". Is this an actual requirement, or will any fairly random solution do? Without knowing the requirements it's really easy to waste a lot of time. If this is a real problem, please explain what the actual requirements are.