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) who's value add up to n:

Lets 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.

Cheers

EDIT: Any help would be great :)

Answer 1

I'm not sure whether I understood you correctly, but try this:

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

do {
    $random = mt_rand(0, $max);

    if (!in_array($random, $array)) {
        $array[] = $random;
        $n--;
    }
} while (n > 0);

Answer 2

Hi, Hope this will help you more....

Approch-1

$aRandomarray = array();
for($i=0;$i<100;$i++)
{
    $iRandomValue = mt_rand(1000, 999);
    if (!in_array($iRandomValue , $aRandomarray)) {
        $aRandomarray[$i] = $iRandomValue;
    }
} 

Approch-2

$aRandomarray = array();
for($i=0;$i<100;$i++)
{
    $iRandomValue = mt_rand(100, 999);
    $sRandom .= $iRandomValue;
}
array_push($aRandomarray, $sRandom);

Answer 3

(assuming positive numbers)

Here is an algorithm you can use for small numbers. Also, it is the start for a better algorithm which has less complexity with bigger numbers.

assert (($diff = $x*($x+1)/2) >= 0);
for ($i=0, $i<$x, $i++)
{
    $answers[i] = i;
}
while ($diff--)
{
    // SOMETIMES THIS FOR LOOP WILL DO NOTHING
    // this is intentional
    for ($i=rand(0, $x); $i<$x; $i++)
        $answers[$i]++;
}

Answer 4

I'm pretty sure this problem is NP-complete. (Hope i'm not being confused). So, if you want something that is simple to implement it will probably have to be some exponential time algorithm.

Answer 5

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.

Answer 6

sorry i missed 'no duplicates' too
-so need to tack on a 'deduplicator' ...i put it in the other question

To generate a series of random numbers with a fixed sum:

• make a series of random numbers (of largest practical magnitude to hide granularity...)
• calculate their sum
• multiply each in series by desiredsum/sum

(basicaly to scale a random series to its new size)

Then there is rounding error to adjust for:

• recalculate sum and its difference from desired sum
• add the sumdiff to a random element in series if it doesnt result in a negative, if it does loop to another random element until fine.
• to be ultratight instead add or subtract 1 bit to random elements until sumdiff=0

Some non-randomness resulting from doing it like this is if the magnitude of the source randoms is too small causing granularity in the result.

I dont have php, but here's a shot -

$n = ;              //size of array
$targsum = ;        //target sum
$ceiling = 0x3fff;  //biggish number for rands
$sizedrands = array();

$firstsum=0;
$finsum=0;

//make rands, sum size
for( $count=$n; $count>0; $count--)
{ $arand=rand( 0, $ceiling );
  $sizedrands($count)=$arand;
  $firstsum+=$arand; }

//resize, sum resize
for( $count=$n; $count>0; $count--)
{ $sizedrands($count)=($sizedrands($count)*$targsum)/$firstsum;
  $finsum+=$sizedrands($count);
  }

//redistribute parts of rounding error randomly until done
$roundup=$targsum-$finsum;

$rounder=1; if($roundup<0){ $rounder=-1; }

while( $roundup!=0 )
{ $arand=rand( 0, $n );
  if( ($rounder+$sizedrands($arand) ) > 0 )
  { $sizedrands($arand)+=$rounder; 
    $roundup-=$rounder; }
  }