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

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 2

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 3

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 4

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.

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

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