For example, say I enter '10' for the amount of values, and '10000' as a total amount.
The script would need to randomize 10 different numbers that all equal up to 10000. No more, no less.
But it needs to be dynamic, as well. As in, sometimes I might enter '5' or '6' or even '99' for the amount of values, and any number (up to a billion or even higher) as the total amount.
How would I go about doing this?
EDIT: I should also mention that all numbers need to be a positive integer
Update: @Joe Blow has the perfect answer. My answer has the special feature of generating chunks of approximately the same size (or at least a difference no bigger than (10000 / 10)), leaving it in place for that reason.
The easiest and fastest approach that comes to my mind is:
Divide 10000 by 10 and store the values in an array. (10 times the value 10000)
Walk through every one of the 10 elements in a for loop.
From each element, subtract a random number between (10000 / 10).
Add that number to the following element.
This will give you a number of random values that, when added, will result in the end value (ignoring floating point issues).
Should be half-way easy to implement.
You'll reach PHP's maximum integer limit at some point, though. Not sure how far this can be used for values towards a billion and beyond.
maybe something like this:
set max amount remaining to the target number
loop for 1 to the number of values you want - 1
get a random number from 0 to the max amount remaining
set new max amount remaining to old max amount remaining minus the current random number
repeat loop
you will end up with a 'remainder' so the last number is determined by whatever is left over to make up the original total.
Generate 10 random numbers till 10000 . Sort them from big to small : g0 to g9
g0 = 10000 - r0
g1 = r0 - r1
...
g8 = r8 - r9
g9 = r9
This will yield 10 random numbers over the full range which add up to 10000.
The correct answer here is unbelievably simple.
Just imagine a white line, let's say 1000 units long.
You want to divide the line in to ten parts, using red marks.
VERY SIMPLY, CHOOSE NINE RANDOM NUMBERS and put a red paint mark at each of those points.
It's just that simple. You're done!
Thus, the algorithm is:
(1) pick nine random numbers between 0 and 1000 (2) put the nine numbers, a zero, and a 1000, in an array (3) sort the array (4) using subtraction get the ten "distances" between array values
You're done.
(Obviously if you want to have no zeros in your final set, in part (1) simply rechoose another random number if you get a collision.)
Ideally as programmers, we can "see" visual algorithms like this in our heads -- try to think visually whatever we do!
Related: http://www.mathworks.cn/matlabcentral/newsreader/view_thread/141395
See this MATLAB package. It is accompanied with a file with the theory behind the implementation.
This function generates random, uniformly distributed vectors, x = [x1,x2,x3,...,xn]', which have a specified sum s, and for which we have a <= xi <= b, for specified values a and b. It is helpful to regard such vectors as points belonging to n-dimensional Euclidean space and lying in an n-1 dimensional hyperplane constrained to the sum s. Since, for all a and b, the problem can easily be rescaled to the case where a = 0 and b = 1, we will henceforth assume in this description that this is the case, and that we are operating within the unit n-dimensional "cube".
This is the implementation (© Roger Stafford):
function [x,v] = randfixedsum(n,m,s,a,b)
% Rescale to a unit cube: 0 <= x(i) <= 1
s = (s-n*a)/(b-a);
% Construct the transition probability table, t.
% t(i,j) will be utilized only in the region where j <= i + 1.
k = max(min(floor(s),n-1),0); % Must have 0 <= k <= n-1
s = max(min(s,k+1),k); % Must have k <= s <= k+1
s1 = s - [k:-1:k-n+1]; % s1 & s2 will never be negative
s2 = [k+n:-1:k+1] - s;
w = zeros(n,n+1); w(1,2) = realmax; % Scale for full 'double' range
t = zeros(n-1,n);
tiny = 2^(-1074); % The smallest positive matlab 'double' no.
for i = 2:n
tmp1 = w(i-1,2:i+1).*s1(1:i)/i;
tmp2 = w(i-1,1:i).*s2(n-i+1:n)/i;
w(i,2:i+1) = tmp1 + tmp2;
tmp3 = w(i,2:i+1) + tiny; % In case tmp1 & tmp2 are both 0,
tmp4 = (s2(n-i+1:n) > s1(1:i)); % then t is 0 on left & 1 on right
t(i-1,1:i) = (tmp2./tmp3).*tmp4 + (1-tmp1./tmp3).*(~tmp4);
end
% Derive the polytope volume v from the appropriate
% element in the bottom row of w.
v = n^(3/2)*(w(n,k+2)/realmax)*(b-a)^(n-1);
% Now compute the matrix x.
x = zeros(n,m);
if m == 0, return, end % If m is zero, quit with x = []
rt = rand(n-1,m); % For random selection of simplex type
rs = rand(n-1,m); % For random location within a simplex
s = repmat(s,1,m);
j = repmat(k+1,1,m); % For indexing in the t table
sm = zeros(1,m); pr = ones(1,m); % Start with sum zero & product 1
for i = n-1:-1:1 % Work backwards in the t table
e = (rt(n-i,:)<=t(i,j)); % Use rt to choose a transition
sx = rs(n-i,:).^(1/i); % Use rs to compute next simplex coord.
sm = sm + (1-sx).*pr.*s/(i+1); % Update sum
pr = sx.*pr; % Update product
x(n-i,:) = sm + pr.*e; % Calculate x using simplex coords.
s = s - e; j = j - e; % Transition adjustment
end
x(n,:) = sm + pr.*s; % Compute the last x
% Randomly permute the order in the columns of x and rescale.
rp = rand(n,m); % Use rp to carry out a matrix 'randperm'
[ig,p] = sort(rp); % The values placed in ig are ignored
x = (b-a)*x(p+repmat([0:n:n*(m-1)],n,1))+a; % Permute & rescale x
return