Create numbers within an array that add up to a set amount

Question

I'm fairly new to PHP - programming in general. So basically what I need to accomplish is, create an array of x amount of numbers (created randomly) whose value add up to n:

Let's say, I have to create 4 numbers that add up to 30. I just need the first random dataset. The 4 and 30 here are variables which will be set by the user.

Essentially something like

x = amount of numbers;
n = sum of all x's combined;

// create x random numbers which all add up to n;

$row = array(5, 7, 10, 8) // these add up to 30

Also, no duplicates are allowed and all numbers have to be positive integers.

I need the values within an array. I have been messing around with it sometime, however, my knowledge is fairly limited. Any help will be greatly appreciated.

Answer 1

First off, this is a really cool problem. I'm almost sure that my approach doesn't even distribute the numbers perfectly, but it should be better than some of the other approaches here.

I decided to build the array from the lowest number up (and shuffle them at the end). This allows me to always choose a random range that will allows yield valid results. Since the numbers must always be increasing, I solved for the highest possible number that ensures that a valid solution still exists (ie, if n=4 and max=31, if the first number was picked to be 7, then it wouldn't be possible to pick numbers greater than 7 such that the sum of 4 numbers would be equal to 31).

$n = 4;
$max = 31;
$array = array();

$current_min = 1;
while( $n > 1 ) {
    //solve for the highest possible number that would allow for $n many random numbers
    $current_max = floor( ($max/$n) - (($n-1)/2) );
    if( $current_max < $current_min ) throw new Exception( "Can't use combination" );
    $new_rand = rand( $current_min, $current_max ); //get a new rand
    $max -= $new_rand; //drop the max
    $current_min = $new_rand + 1; //bump up the new min
    $n--; //drop the n
    $array[] = $new_rand; //add rand to array
}
$array[] = $max; //we know what the last element must be
shuffle( $array );

EDIT: For large values of $n you'll end up with a lot of grouped values towards the end of the array, since there is a good chance you will get a random value near the max value forcing the rest to be very close together. A possible fix is to have a weighted rand, but that's beyond me.