Randomly Generate a set of numbers of n length totaling x

Question

I'm working on a project for fun and I need an algorithm to do as follows: Generate a list of numbers of Length n which add up to x

I would settle for list of integers, but ideally, I would like to be left with a set of floating point numbers.

I would be very surprised if this problem wasn't heavily studied, but I'm not sure what to look for.

I've tackled similar problems in the past, but this one is decidedly different in nature. Before I've generated different combinations of a list of numbers that will add up to x. I'm sure that I could simply bruteforce this problem but that hardly seems like the ideal solution.

Anyone have any idea what this may be called, or how to approach it? Thanks all!

Edit: To clarify, I mean that the list should be length N while the numbers themselves can be of any size.

edit2: Sorry for my improper use of 'set', I was using it as a catch all term for a list or an array. I understand that it was causing confusion, my apologies.

Answer 1

This is how to do it in Python

import random

def random_values_with_prescribed_sum(n, total):
    x = [random.random() for i in range(n)]
    k = total / sum(x)
    return [v * k for v in x]

Basically you pick n random numbers, compute their sum and compute a scale factor so that the sum will be what you want it to be.

Note that this approach will not produce "uniform" slices, i.e. the distribution you will get will tend to be more "egalitarian" than it should be if it was picked at random among all distribution with the given sum.

To see the reason you can just picture what the algorithm does in the case of two numbers with a prescribed sum (e.g. 1):

The point P is a generic point obtained by picking two random numbers and it will be uniform inside the square [0,1]x[0,1]. The point Q is the point obtained by scaling P so that the sum is required to be 1. As it's clear from the picture the points close to the center of the have an higher probability; for example the exact center of the squares will be found by projecting any point on the diagonal (0,0)-(1,1), while the point (0, 1) will be found projecting only points from (0,0)-(0,1)... the diagonal length is sqrt(2)=1.4142... while the square side is only 1.0.

Answer 2

Actually, you need to generate a partition of x into n parts. This is usually done the in following way: The partition of x into n non-negative parts can be represented in the following way: reserve n + x free places, put n borders to some arbitrary places, and stones to the rest. The stone groups add up to x, thus the number of possible partitions is the binomial coefficient (n + x \atop n).

So your algorithm could be as follows: choose an arbitrary n-subset of (n + x)-set, it determines uniquely a partition of x into n parts.

In Knuth's TAOCP the chapter 3.4.2 discusses random sampling. See Algortihm S there.

---

Algorithm S: (choose n arbitrary records from total of N)

1. t = 0, m = 0;
2. u = random, uniformly distributed on (0, 1)
3. if (N - t)*u >= n - m, skip t-th record and increase t by 1; otherwise include t-th record in the sample, increase m and t by 1
4. if M < n, return to 2, otherwise, algorithm finished

---

The solution for non-integers is algorithmically trivial: you just select arbitrary n numbers that don't sum up to 0, and norm them by their sum.

Answer 3

If you want to sample uniformly in the region of N-1-dimensional space defined by x1 + x2 + ... + xN = x, then you're looking at a special case of sampling from a Dirichlet distribution. The sampling procedure is a little more involved than generating uniform deviates for the xi. Here's one way to do it, in Python:

xs = [random.gammavariate(1,1) for a in range(N)]
xs = [x*v/sum(xs) for v in xs]

If you don't care too much about the sampling properties of your results, you can just generate uniform deviates and correct their sum afterwards.

Answer 4

Here is a version of the above algorithm in Javascript

    function getRandomArbitrary(min, max) {
        return Math.random() * (max - min) + min;
    };
    function getRandomArray(min, max, n) {
        var arr = [];
        for (var i = 0, l = n; i < l; i++) {
            arr.push(getRandomArbitrary(min, max))
        };
        return arr;
    };
    function randomValuesPrescribedSum(min, max, n, total) {
        var arr = getRandomArray(min, max, n);
        var sum = arr.reduce(function(pv, cv) { return pv + cv; }, 0);
        var k = total/sum;
        var delays = arr.map(function(x) { return k*x; })
        return delays;
    };

You can call it with

var myarray = randomValuesPrescribedSum(0,1,3,3);

And then check it with

var sum = myarray.reduce(function(pv, cv) { return pv + cv;},0);

Answer 5

In python:

a: create a list of (random #'s 0 to 1) times total; append 0 and total to the list

b: sort the list, measure the distance between each element

c: round the list elements

import random
import time

TOTAL       = 15
PARTS       = 4
PLACES      = 3

def random_sum_split(parts, total, places):

    a = [0, total] + [random.random()*total for i in range(parts-1)]
    a.sort()
    b = [(a[i] - a[i-1]) for i in range(1, (parts+1))]
    if places == None:
        return b
    else:    
        b.pop()
        c = [round(x, places) for x in b]  
        c.append(round(total-sum(c), places))
        return c

def tick():

    if info.tick == 1:

        start = time.time()
        alpha = random_sum_split(PARTS, TOTAL, PLACES)
        end = time.time()  

        log('alpha: %s' % alpha)
        log('total: %.7f' % sum(alpha))
        log('parts: %s' % PARTS)
        log('places: %s' % PLACES)
        log('elapsed: %.7f' % (end-start))

yields:

[2014-06-13 01:00:00] alpha: [0.154, 3.617, 6.075, 5.154]
[2014-06-13 01:00:00] total: 15.0000000
[2014-06-13 01:00:00] parts: 4
[2014-06-13 01:00:00] places: 3
[2014-06-13 01:00:00] elapsed: 0.0005839

to the best of my knowledge this distribution is uniform

Answer 6

This code does a reasonable job. I think it produces a different distribution than 6502's answer, but I am not sure which is better or more natural. Certainly his code is clearer/nicer.

import random

def parts(total_sum, num_parts):
  points = [random.random() for i in range(num_parts-1)]
  points.append(0)
  points.append(1)
  points.sort()

  ret = []
  for i in range(1, len(points)):
    ret.append((points[i] - points[i-1]) * total_sum)
  return ret

def test(total_sum, num_parts):
  ans = parts(total_sum, num_parts)
  assert abs(sum(ans) - total_sum) < 1e-7
  print ans

test(5.5, 3)
test(10, 1)
test(10, 5)