5

Not sure if this exact question's been asked before, though a similar question has been asked here. Essentially, what I'm trying to is generate random integers of a minimum size that still sum up to a certain value (an invariant is that the sum / (number of randoms you want) is greater than the minimum value. Here's a sad attempt I coded up:

import java.util.Arrays;
import java.util.Random;

public class ScratchWork {

    private static Random rand = new Random();


    public static void main(String[] args) {
            int[] randoms = genRandoms(1000, 10, 30);
            for (int i = 0; i<randoms.length; i++) sop("Random Number "+ (i+1) + ": " + randoms[i]);
            sop("Sum: " + sum(randoms));
    }

    public static int sum(int[] array) { int sum = 0; for (int i : array) sum+=i; return sum; }

    public static int[] genRandoms(int n, int numberOfRandoms, int min) {
        if (min > n/numberOfRandoms) throw new UnsupportedOperationException();
        int[] intRandArray = {0};
        while (sum(intRandArray) != n) {
            ////////////////////////
            // See https://stackoverflow.com/questions/2640053/getting-n-random-numbers-that-the-sum-is-m
            Double[] randArray = new Double[numberOfRandoms];
            double workerSum = 0;
            for (int i = 0; i<numberOfRandoms; i++) {
                randArray[i] = ((double)rand.nextInt(n-1)+1);
                workerSum += randArray[i];
            }

            for (int i = 0; i<randArray.length; i++) {
                randArray[i] = n*(randArray[i]/(workerSum));
            }
            /////////////////////////

            while (existsSmallerNumThanMin(randArray, min)) 
                randArray = continueToFix(randArray, min);

            //Convert doubles to ints
            intRandArray = new int [randArray.length];
            for (int i = 0; i < intRandArray.length; i++) 
                intRandArray[i] = (int)Math.round(randArray[i]);
        }
        return intRandArray;
    }

    public static boolean existsSmallerNumThanMin(Double[] randArray, int min) {
        for (double i : randArray) if (i < (double)min) return true;
        return false;
    }

    public static Double[] continueToFix(Double[]randArray, int min) {
        Double[] tempArray = Arrays.copyOf(randArray, randArray.length);
        Arrays.sort(tempArray);
        int smallest = Arrays.asList(randArray).indexOf(tempArray[0]);
        int largest = Arrays.asList(randArray).indexOf(tempArray[tempArray.length-1]);

        double randomDelta = rand.nextInt(min);

        randArray[smallest]+=randomDelta;
        randArray[largest]-=randomDelta;
        return randArray;
    }

    public static void sop(Object s) { System.out.println(s); }

}

This is neither an elegant nor high-performing way to do this... It also doesn't seem to work well (if at all) when passed in, say, (100,10,10), which only allows for the number 10 in the array. The distribution of the random numbers is also pretty bad.

Is there an elegant approach to this??

Also, my end goal is to implement this in Objective-C, though I'm still just learning the ropes of that language, so any tips for doing this in that language would be greatly appreciated.

5
  • To get statistically sound answers, maybe also try stats.stackexchange.com
    – Thilo
    Jan 13, 2012 at 7:34
  • Should all possible combinations be equally likely? And how do you count them, i.e. is 5+5 one combination or two, and 2+4 the same combination as 4+2 or not?
    – Thilo
    Jan 13, 2012 at 7:56
  • All combinations being equally likely sounds a little nontrivial, but it doesn't matter how they're counted imho.
    – benjammin
    Jan 13, 2012 at 8:05
  • You mention two different restraints on the minimum value: a minimum value for each individual number, and a minimum value for the mean. Which of these do you want to restrain? The former is trivial, as it implies the latter. The latter is trivial if the sum is fixed.
    – outis
    Jan 13, 2012 at 8:24
  • The former (each number should be at least a minimum value, inclusive).
    – benjammin
    Jan 13, 2012 at 8:38

5 Answers 5

5

I did some more testing, and my Java implementation is broken. I think my algorithm is bad.

How about something like getting N random numbers in [0,1] and normalize the results based on their sums (different than the desired sum). Then multiply these values against the desired number sum.

This assumes the minimum size is 0. Generalizing this to maintain a minimum for each result is simple. Just feed in sum - min * n for sum. Add min to all the results.

To avoid potential floating point issues, you can do something similar with using a range of integer values that are logically on the scale [0,M] (M arbitarily large) instead of [0,1]. The idea is the same in that you "normalize" your random results. So lets say you get a random sum of N (want N to have to be a multiple of sum+1... see REMARK). Divy N up by sum+1 parts. The first part is 0, second is 1, ..., last is sum. Each random value looks up its value by seeing what part of N it belongs to.

REMARK: If you are okay with an arbitrarily small amount of bias, make each die roll a magnitude larger than sum (might want BigInteger for this). Let N be the sum. Then N = k*sum + rem where rem < sum. If N is large, then rem / k -> 0, which is good. N is probabilistically large if M is large.

Algorithm psuedo code:

F(S, N):
    let R[] = list of 0's of size N
    if S = 0: return R[]
    for 0 <= i < N
        R[i] = random integer in [0, M] -- inclusive and (M >= S). M should be an order larger than S. A good pick might be M = 1000*S*N. Not sure though. M should probably be based on both S and N though or simply an outragously large number.
    let Z = sum R[]
    for 0 <= i < N
        R[i] = (Z mod R[i]) mod (S+1)
    return R[]

Java implementation:

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;


public class Rand {
    private final Random rand;
    
    public Rand () {
        this(new Random());
    }
    
    public Rand (Random rand) {
        this.rand = rand;
    }
    
    public int[] randNums (int total, int minVal, int numRands) {
        if (minVal * numRands > total) {
            throw new IllegalArgumentException();
        }
        int[] results = randNums(total - minVal * numRands, numRands);
        for (int i = 0; i < numRands; ++i) {
            results[i] += minVal;
        }
        return results;
    }

    private int[] randNums (int total, int n) {
        final int[] results = new int[n];
        if (total == 0) {
            Arrays.fill(results, 0);
            return results;
        }
        final BigInteger[] rs = new BigInteger[n];
        final BigInteger totalPlus1 = BigInteger.valueOf(total + 1L);
        while (true) {
            for (int i = 0; i < n; ++i) {
                rs[i] = new BigInteger(256, rand);
            }
            BigInteger sum = BigInteger.ZERO;
            for (BigInteger r : rs) {
                sum = sum.add(r);
            }
            if (sum.compareTo(BigInteger.ZERO) == 0) {
                continue;
            }
            for (int i = 0; i < n; ++i) {
                results[i] = sum.mod(rs[i]).mod(totalPlus1).intValue();
            }
            return results;
        }
    }
    
    public static void main (String[] args) {
        Rand rand = new Rand();
        Map<Integer, Integer> distribution = new TreeMap<Integer, Integer>();
        final int total = 107;
        final int minVal = 3;
        final int n = 23;
        for (int i = total - (n-1) * minVal; i >= minVal; --i) {
            distribution.put(i, 0);
        }
        for (int i = 0; i < 100000; ++i) {
            int[] rs = rand.randNums(total, minVal, n);
            for (int r : rs) {
                int count = distribution.get(r);
                distribution.put(r, count + 1);
            }
        }
        System.out.print(distribution);
    }
    
}
4
  • Not sure if it is safe to leave the real of integers. Also, what do you do with numbers that are below the minimum? Start all over seems to be safest.
    – Thilo
    Jan 13, 2012 at 7:51
  • Alright, I'll implement your algo and try it out (I don't really have a natural intuition for this sort of thing:P )
    – benjammin
    Jan 13, 2012 at 8:36
  • Hmmm... Had some issues with the implementation
    – benjammin
    Jan 13, 2012 at 10:54
  • @BenM: Whoops, forgot to do another need mod in my psuedo code. R[i] = Z mod R[i] -> R[i] = (Z mod R[i]) mod (S+1) Jan 13, 2012 at 18:41
3

Does this do what you need?

import java.util.Arrays;
import java.util.Random;

public class ScratchWork {
    static Random rng = new Random();

    public static int randomRange(int n) {
        // Random integer between 0 and n-1
        assert n > 0;
        int r = rng.nextInt();
        if(r >= 0 && r < Integer.MAX_VALUE / n * n) {
            return r % n;
        }
        return randomRange(n);
    }

    public static int[] genRandoms(int n, int numberOfRandoms, int min) {
        int randomArray[] = new int[numberOfRandoms];
        for(int i = 0; i < numberOfRandoms; i++) {
            randomArray[i] = min;
        }
        for(int i = min*numberOfRandoms; i < n; i++) {
            randomArray[randomRange(numberOfRandoms)] += 1;
        }
        return randomArray;
    }

    public static void main(String[] args) {
        int randoms[] = genRandoms(1000, 10, 30);
        System.out.println(Arrays.toString(randoms));

    }
}
3
  • +1. That looks good. In words: Start all numbers at the minimum, and sprinkle +1 randomly over them.
    – Thilo
    Jan 13, 2012 at 7:52
  • 1
    OTOH: Isn't this terribly biased towards an equal distribution? If you want 3 numbers to add up to 100, minimum 1, something like 80:10:10 should appear once in a while.
    – Thilo
    Jan 13, 2012 at 7:54
  • You're right @Thilo. Suppose we have two positive numbers, (x, y) which add to 10. There should be a one in eleven chance that (0, 10) is chosen. But for this algorithm, it's one in 2^10.
    – wye.bee
    Jan 13, 2012 at 7:58
2

Based on the revised requirements in the comments below.

public static int[] genRandoms(int total, int numberOfRandoms, int minimumValue) {
    int[] ret = new int[numberOfRandoms];
    Random rnd = new Random();
    int totalLeft = total;
    for (int i = 0; i < numberOfRandoms; i++) {
        final int rollsLeft = numberOfRandoms - i;
        int thisMax = totalLeft - (rollsLeft - 1) * minimumValue;
        int thisMin = Math.max(minimumValue, totalLeft / rollsLeft);
        int range = thisMax - thisMin;
        if (range < 0)
            throw new IllegalArgumentException("Cannot have " + minimumValue + " * " + numberOfRandoms + " < " + total);
        int rndValue = range;
        for (int j = 0; j * j < rollsLeft; j++)
            rndValue = rnd.nextInt(rndValue + 1);
        totalLeft -= ret[i] = rndValue + thisMin;
    }
    Collections.shuffle(Arrays.asList(ret), rnd);
    return ret;
}

public static void main(String... args) throws IOException {
    for (int i = 100; i <= 1000; i += 150)
        System.out.println("genRandoms(" + i + ", 30, 10) = " + Arrays.toString(genRandoms(1000, 30, 10)));
}

prints

genRandoms(100, 30, 10) = [34, 13, 22, 20, 26, 12, 30, 45, 22, 35, 108, 20, 31, 53, 11, 35, 20, 11, 18, 32, 14, 30, 20, 19, 31, 31, 151, 45, 25, 36]
genRandoms(250, 30, 10) = [30, 27, 25, 34, 28, 33, 34, 82, 45, 30, 24, 26, 26, 45, 19, 18, 95, 28, 22, 30, 30, 25, 38, 11, 18, 27, 77, 26, 26, 21]
genRandoms(400, 30, 10) = [48, 25, 19, 22, 36, 65, 24, 29, 49, 24, 11, 30, 33, 41, 37, 33, 29, 36, 28, 24, 32, 12, 28, 29, 29, 34, 35, 28, 27, 103]
genRandoms(550, 30, 10) = [25, 44, 72, 36, 55, 41, 11, 33, 20, 21, 33, 19, 29, 30, 13, 39, 54, 26, 33, 30, 40, 32, 21, 31, 61, 13, 16, 51, 37, 34]
genRandoms(700, 30, 10) = [22, 13, 24, 26, 23, 61, 44, 79, 69, 25, 29, 83, 29, 35, 25, 13, 33, 32, 13, 12, 30, 26, 28, 26, 14, 21, 26, 13, 84, 42]
genRandoms(850, 30, 10) = [11, 119, 69, 14, 39, 62, 51, 52, 34, 16, 12, 17, 28, 25, 17, 31, 32, 30, 34, 12, 12, 38, 11, 32, 25, 16, 31, 82, 18, 30]
genRandoms(1000, 30, 10) = [25, 46, 59, 48, 36, 32, 29, 12, 27, 34, 33, 14, 12, 30, 29, 31, 25, 16, 34, 44, 25, 50, 60, 32, 42, 32, 13, 41, 51, 38]

IMHO, Shuffling the result improves the randomness of the distribution.

14
  • I get strange output on input (12,3,100) (3 random numbers >= 12 that sum up to 100).
    – benjammin
    Jan 13, 2012 at 9:17
  • I thought n was the maximum, not the minimum value. Jan 13, 2012 at 9:19
  • 1
    Solid, plus I can also easily implement this in objective-c. Thanks!
    – benjammin
    Jan 13, 2012 at 10:53
  • 1
    @Thilo similar. The last value has to be total - totalSoFar so the min need to increase at certain points. Jan 13, 2012 at 12:06
  • 1
    Umm... you have a 108 in genRandoms(100, 30, 10). That's not good. Jan 13, 2012 at 18:43
1

Maybe a recursive approach:

  • if numberOfRandoms is 1, return n
  • if numberOfRandoms is x+1
    • get a random integer (myNumber) between min and n-min*x (so that at least min is left for each of the remaining x numbers)
    • get the remaining x that add up to n-myNumber
3
  • Sounds good like a pretty nifty solution to me! I'll try implementing it.
    – benjammin
    Jan 13, 2012 at 7:44
  • I bet this will generate a biased outcome. Jan 13, 2012 at 7:46
  • Yeah, I am not sure. For a proper analysis we really need to ask the folks at stats.stackexchange.com
    – Thilo
    Jan 13, 2012 at 7:48
0

This is a utility method for generating a fixed length random number.

    public final static String createRandomNumber(long len) {
    if (len > 18)
        throw new IllegalStateException("To many digits");
    long tLen = (long) Math.pow(10, len - 1) * 9;

    long number = (long) (Math.random() * tLen) + (long) Math.pow(10, len - 1) * 1;

    String tVal = number + "";
    if (tVal.length() != len) {
        throw new IllegalStateException("The random number '" + tVal + "' is not '" + len + "' digits");
    }
    return tVal;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.