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

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 have this so far :

function randomDistinctPartition($n, $max)
{
    $partition= array();
    for($i=1; $i < $n; $i++) {
        $maxSingleNumber = $max - $n;
        $partition[] = $number = rand(1, $maxSingleNumber);
        $max -= $number;
			
    }
    $partition[] = $max;
    return $partition;
}

However it does not work against duplicates and negative integers. Any assistance in helping me achieve this will be greatly appreciated.

Cheers.

You have not checked that the number already exists in the array - for example try using in_array() to check for duplicates?

I would minus off the random number from the max and generate a new random number based on 1 to the new max number.


function randomDistinctPartition($n, $max)
{
    $partition= array();
    for($i=1; $i < $n; $i++) {
        $rand = rand(1,$max);
        while(in_array($rand,$partition))
        {
           $rand = rand(1,$max);
        }
        $partition[] = $rand;
        $max = $max - $rand;
    }
    return $partition;
}

I am having trouble implementing a needle in a haystack with the in_array function. Mainly because I cant wrap my around the fact that the needle and the haystack are one thing in this code.

The code above does not seem to give me accurate numbers that add up to $max?

wha???

Throwing this on the fly, so it might be off a bit but…


function RandArrayToSum($numvalues,$total) {
   $subtotal = $total;
   $sigma = (2+$numvalues+($numvalues^2))/2 // Sum Of All Integers 1...NumValues
   if($total <= $sigma) {
       return array("Failed: Impossible Array");
   }
   for($i = 1; $i < $numvalues; $i++) {
       $num = rand(1,($subtotal - (2+($numvalues - $i)+(($numvalues-$i)^2)/2)));
       $out[] = $num;
       $subtotal -= $num;
   }
   $out[] = $subtotal;
   return $out;
}

Mkay, swing 2… this time with uniqueness, although the uniqueness-ensurer allows the possibility of having a 0 in the array (if there are 2 1’s)


function RandArrayToSum($numvalues,$total) {
   $subtotal = $total;
   $sigma = (2+$numvalues+($numvalues^2))/2; // Sum Of All Integers 1...NumValues
   if($total <= $sigma) {
       return array("Failed: Impossible Array");
   }
   for($i = 1; $i < $numvalues; $i++) {
       $num = rand(1,($subtotal - (2+($numvalues - $i)+(($numvalues-$i)^2)/2)));
       $out[] = $num;
       $subtotal -= $num;
   }
   $out[] = $subtotal;
   while(count($out) != count(array_unique($out))) {
       $i = 0;
       while($i < count($out)) {
          for ($j = $i+1; $j < count($out); $j++) {
               if ($out[$i] === $out[$j]) {
                   $out[$i]++;
                   $out[$j]--;
                   $i = count($out);
                   $j = count($out);
                }
          }
       }
   }
   return $out;
} 

My first thought is to start with an array created using array_fill to get a starting point.

Since the $sum isn’t always going to be evenly divisible by the $num I’m thinking a modulo will be needed. If I save the remainder of a modulo operation in a variable, I can subtract that from $sum and array_fill a starting point array with $num elements of $msum / $num.

So not to lose the remainder of the modulo, and in order to maintain whole numbers, I’ll add the remainder to the value of the first array element.

At this point I have an array of values which the sum of is $sum, all duplicate values with the exception of $arr[0]. It looks like we don’t want duplicates though.

So what I’ll do is use a while loop to continuously see if $num is equal to the length of array_unique($arr). If the numbers are equal, all items are unique, there are enough items, and the loop can exit.

Within this loop I’ll randomly select two elements of the array to alter. I’ll add to one of the items and subtract an equal amount from the other item. This way the numbers will change while I still have the correct number of elements in the array.

Here’s my function.

function it($num, $sum)
{
	$_num		= $num - 1;
	$mod		= $sum % $num;
	$returns	= array_fill(0, $num, ($sum - $mod) / $num);
	$returns[0]	+= $mod;
	
	while($num != count(array_unique($returns)))
	{
		$a = mt_rand(0, $_num);
		$b = mt_rand(0, $_num);
		while($a == $b)
		{
			$b = mt_rand(0, $_num);
		}
		$c = mt_rand(1, max($returns[$a], $returns[$b]) - 1);
		
		if($returns[$a] > $returns[$b])
		{
			$returns[$a] -= $c;
			$returns[$b] += $c;
		}
		else
		{
			$returns[$a] += $c;
			$returns[$b] -= $c;
		}
	}
	
	return $returns;
}

make an array $terms with numbers 1 to x
you want random, so shuffle() it
start generating k-combinations, and stop/succeed when you generate one that sums correctly. If you exhaust all k-combinations, then no solution was possible.

You don’t need rand(), array_unique(), or anything like that if you generate the k-combinations correctly. The algorithm has a deterministic upper bound, although it can be very large depending on what x and n are.

You can optimize a ton if you’re willing to sacrifice how random the distribution is, but the above approach should be perfectly random(well, as random as the shuffle() step is).

You can optimize without sacrifice by making $terms 1 to (n - sum(1 to x) - 1)
You can fail fast when sum($terms) < n
There’s probably more ways to fail fast when a solution isn’t possible.

Sounds like homework :slight_smile: