CODEWITHSUNDEEP
random
Wen Chen
Wen Chen

Reputation: 53

generate random integers with fixed sum and constraints

How to generate 6 random integers which add up to 8, and each one is less than or equal to 2?

eg. 1,2,1,2,2,0

For far I have found the method which give the random integers with fixed sum but how to impose the constraints on these integers.

Upvotes: 5

Views: 3424

Answers (3)

John Coleman
John Coleman

Reputation: 51998

I would recommend a hit-and-miss approach to guarantee a uniform distribution of generated sequences satisfying the constraint. It is easy to work out that the probability of 6 random integers in {0,1,2} adding up to 8 is roughly 12.3%, so not too many trials are needed before a hit. Here is a Python implementation:

import random

def randNums(n,a,b,s):
    #finds n random ints in [a,b] with sum of s
    hit = False
    while not hit:
        total, count = 0,0
        nums = []
        while total < s and count < n:
            r = random.randint(a,b)
            total += r
            count += 1
            nums.append(r)
        if total == s and count == n: hit = True
    return nums

Here is the output from 5 runs:

>>> for i in range(5): print(randNums(6,0,2,8))

[2, 1, 0, 2, 1, 2]
[0, 2, 2, 1, 1, 2]
[2, 2, 0, 2, 0, 2]
[2, 2, 0, 1, 1, 2]
[1, 2, 1, 1, 1, 2]

On Edit: I was curious about the exact probabilities so wrote a program to exhaustively enumerate all possibilities. Random sequences of length 6 in {0,1,2} can be thought of as random integers in 0 to 3^6-1 = 728 written in base 3. Just calculate the digit sums for base-3 numbers in that range and see which = 8:

def toBase3(n):
    digits = []
    q,r = divmod(n,3)
    while q > 0:
        digits.append(r)
        q,r = divmod(q,3)
    digits.append(r)
    return ''.join(str(i) for i in reversed(digits))

def dsum(s):
    return sum(int(d) for d in s)

hits = []
for n in range(729):
    s = toBase3(n)
    if dsum(s) == 8: hits.append(s)

hits = [('0'*(6-len(s)))+s for s in hits] #left-pad with '0' if needed

s = ''.join(hits)

print("%d valid sequences for prob. of %f" % (len(hits),len(hits)/3.0**6))
print("%d zeros in those sequences for a prob. of %f" % (s.count('0'),s.count('0')/540.0))
print("%d ones in those sequences for a prob. of %f" % (s.count('1'),s.count('1')/540.0))
print("%d twos in those sequences for a prob. of %f" % (s.count('2'),s.count('2')/540.0))

Output:

90 valid sequences for prob. of 0.123457
90 zeros in those sequences for a prob. of 0.166667
180 ones in those sequences for a prob. of 0.333333
270 twos in those sequences for a prob. of 0.500000

As an odd curiosity, the probability that such a random sequence of length 6 sums to 8, with more decimal places displayed, is 

90/729 = 0.123456790 (repeating)

I didn't realize that there was such a nice probability interpretation of the pleasing decimal 0.1234567. It's a pity that 8 isn't after the 7.

Upvotes: 2

Jimbo Jonny
Jimbo Jonny

Reputation: 3579

First, not all of it can be truly random, since those requirements make a few things necessary.

For example, there MUST be at least two 2's in order for 6 total numbers from the set {0,1,2} to make it to 8. So two of our end integers are preordained. May as well not waste energy figuring them out because of that. So that starts us off at 2,2,?,?,?,?.

Now that leaves us with a challenge consisting of getting 4 numbers from the set {0,1,2} that equal 4. The possible combinations for that are (not counting the 0's) two 2's, one 2 and two 1's, and four 1's. Literally only 3 possible combos. So it makes sense to just set them into an array and pick one at random...and those arrays can start with the two 2's we already know will be needed. So:

var possibles = [
    [2,2,2,2,0,0],
    [2,2,2,1,1,0],
    [2,2,1,1,1,1]
];

var randomInd = Math.floor( Math.random()*possibles.length ); // random number from 0-2
var myArr = possibles[randomInd]; // picks a random entry from possibles

Now that we've got a random Array consisting of the possible ways it could go down, we just have to shuffle it up. We can use a standard shuffling function for that:

function shuffle(arr)
{
    var curInd = arr.length, tempVal, randInd;
    while (0 !== curInd) {
        randInd = Math.floor(Math.random()*curInd);
        curInd -= 1;
        tempVal = arr[curInd];
        arr[curInd] = arr[randInd];
        arr[randInd] = tempVal;
    }
}

shuffle(myArr);
alert(myArr); // will give "random" sequence

You could also "weight" certain combinations by better representing them in the possibles array (i.e. make 2 entries of a certain combo instead of 1).

Note - I don't see any specific language required, so for anyone curious that's javascript. A JSFiddle can be seen of it working here: https://jsfiddle.net/6xaeLp4g/

Upvotes: 2

Thilo
Thilo

Reputation: 262504

How about this:

  1. start the array with all zeros.
  2. randomly choose an array index, and add one to that position in the array. If it is already at two, don't do it, retry until it succeeds.
  3. do step 2 eight times

This will not result in uniformly distributed integers on [0,2] (but you did not say what distribution you need), the numbers will skew towards equal heights across the array.

Upvotes: 3

Related Questions