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.
-
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); }Igor Zelaya : you have to check that arbitraryN is not grater than 270JaredPar : @Igor, the solution is for the value 200. If it were a variable solution then yes i would need to check for a constant.Igor Zelaya : @JaredPar, it says "or an arbitraryN".lc : Stop picking nits, the code is easily changeable from 200 to a different number. You can even make it a parameter. Also, you don't HAVE to check it's not greater than 270. It's just nice to do some argument checking. Either way, it'll just infinite-loop and you know something is amiss.lc : Oh, and don't forget, if you do argument-checking, you should also throw if arbitraryN is less than 30.David Schmitt : Creating a new Random() each time will kill the performance and (through reseeding) also the quality of your solution. -
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.
Adam Peck : What if the 29 are all ones? He wanted the numbers in the range of 1-9.Jason Punyon : Maybe I was a bit hasty in adding my big-O statement. Either way. In a trial that matches the requirements, (30 numbers that add up to 200) he can only generate 29 numbers. The 30th number won't be random.lc : Not quite. Definitely on the right track though, but Adam Peck is right about the requirements. If the first 29 numbers are 1, the 30th number has to be 171, which is out of the 1-9 bounds.Robert Gould : @JPunyon in this case I think you should generate 30 numbers, and if they fail the test (==300) you throwaway the whole series and start over.lc : But that just brings us to JaredPar's algorithm. There's a possibility it'll never give you the answer.lc : Very good point with the question's wording. I had made an assumption with the question and provided a way to get one of those sets, because generating 30 random numbers would almost always fail to meet the criteria. And I think you're right about the Pigeonhole Principle, but it's been a while. -
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).
-
Algorithm:
- Set total = 200 (or whatever)
- Generate Random number between 1-9
- Check if (total - newRandomNumber >= 0), if no goto 6
- total -= newRandomNumber
- Add newRandomNumber to array, goto 2.
- newRandomNumber = total
- Add newRandomNumber to array if newRandomNumber != 0
- End
Simucal : This is a pretty good method I think. The only problem is, you can't control the number of digits with this method. -
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
lengthto benumDigitsfor readability.Simucal : Yea, but how will that guarantee a number of digits?lc : "length" is the number of digits. It zeroes in on the target sum and generates a "length" number of "nextNumber"sSimucal : @lc, interesting.. nice.lc : Thanks. JPunyon was on the right track, saying the 30th number would be defined by the first 29. Bounding each digit to 1-9 actually says that the last N numbers are defined by the first 30-N, where N varies two-dimensionally. Also we shouldn't force 7,9* at the end, when we can have 8,8,9* instead.Jason Punyon : I may be missing it because its late, but how does shuffling eliminate the bias?lc : Because the biased numbers aren't all grouped at the tail anymore.Jason Punyon : So spreading out the biased numbers makes them more random? Why would we ever worry about psuedorandom number sequences if we could just shuffle them around to get truly random number sequences?lc : No, no. Think about how you suggested that the 30th number was defined by the first 29. It's the same idea here, except it's not 30 and 29, it's N and 30-N, where N varies as the list becomes defined. As you choose numbers, there are only certain combinations left that are guaranteed to work.lc : ...That being said, if you happen to choose a bunch of low numbers, you're going to HAVE to choose high ones later to reach your target sum. And vice versa. Shuffling it hides the fact that the numbers were chosen in a certain order.Jason Punyon : I'll think overnight and come back in the morning...I've destroyed my work Friday already by staying up this late :-)lc : Haha, fair enough. :-) To put it in other words, just like you were saying, your earlier choices determine what your later choices have to be. It is still random because you always sample from the largest pool of possibilities available (every number is randomly chosen until you cannot anymore).Simucal : We also don't need Edit updates, just title your edits when you make them.. we have wiki-version control on all questions if we are curious about edits ;). Very good answer btwSpencer Ruport : +1 Didn't mean to steal your thunder here. I was working on a solution and posted before I saw this.lc : @Simucal Yeah, thank you, and I did think about adding them or not. I decided to add the Edit updates because I thought the 1-based bit was a good note to have, and because "length" was referenced in the comments. -
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
Simucal : Does this get 30 random digits that add up to N? Or a random number of digits?lc : Looks like a random number of digits and could actually go over the sum by up to 8.Rulas : lol I forgot that 30 was needed... -
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; }Jason Punyon : The only way this algorithm completes is if the last number you choose coincidentally matches the only number that completes the set (sums to 200). Doing it enough times until you match doesn't make it any more random than setting it outright.Igor Zelaya : you are right, I will fix it... -
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 betweenUPPERandLOWERincreases the more flexible this becomes.lc : Yes, that's basically what I was getting at in my answer, and yes, you should shuffle (good idea on a shuffle algorithm btw). For reference the tail numbers may not necessarily be lower; they could be higher too. But either way, there will be a statistical bias.Spencer Ruport : Yeah I realized that while I was at dinner. My bad. :D Fixed.lc : Yup, and no worries about "thunder-stealing" here. I was just pointing out that we had the same idea. (You also had the shuffle algorithm and time to test.) And for the record, I gave you +1 a while ago. :-)Fatal510 : Great job... it's what i wanted. -
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%.
lc : Right, a random list of 30 numbers 1-9 will not necessarily add up to a specific N. But if you taper the bounds as the numbers get generated, you can coerce the list to be of a certain length. Take a look at my answer.simonjpascoe : if you edit the bounds so you're always picking something more favourable, you're not sampling from 1-9 each time.lc : The point is, you CAN'T sample from 1-9 each time like you said. Otherwise you'd end up with JaredPar's algorithm, which, like you say, would end about 0.5% of the time. You have to edit the bounds to fit the requirements of the question - generate a random list that adds up to N.lc : ...That is, sample from 1-9 as much as you can, but as the list becomes more defined, you sample from a smaller set of numbers. Your earlier choices determine what your later choices have to be. It is still random because you always sample from the largest pool of possibilities available.simonjpascoe : I think that conditioning your sample based on the previous outcomes introduces a strong bias. Undershooting your goal sum value by the less than 9 and then forcing the last one will get you the closest i think. -
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!
-
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.
-
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.
pro3carp3 : This is how I would approach the problem also.Jason Punyon : Wow has this been fun lc! My first impression is that this might look right...but how do you know this doesn't introduce the same bias as before? Won't it produce the same solution set and distribution as the first lc-Spencer algorithm? If you've got any links I'd love to see them.Jason Punyon : Now that I think about it I think I might remember this algorithm from numerical recipes in C...I have to look backlc : Well, the problem as defined (or rather as we re-defined it) produces the same bias either way, and yes it will produce the same solution sets as the first one, but the order may be different. This one doesn't require a shuffle, so it preserves the first random order (whatever that means)...lc : ...This algorithm, however, should theoretically produce the exact same output distribution as the naive (JaredPar's) algorithm (preserving order). The difference being that this will always exit. But, since the shuffling algorithm itself takes a random seed, everything is relatively equivalent.lc : Btw, I'm curious as to what you can dig up (re: numerical recipes in C). -
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.
-
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 -
Backtracking?
-
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.
0 comments:
Post a Comment