split the number 100 into arrays of numbers that add up to 100

[tallberg]

Hi

 

Im looking for a way to split the numbers 100 into arrays of number that add up to 100.

 

Example

 

firstArray[] = 1

firstArray[] = 99

 

secondArray[] = 2

secondArray[] = 98

 

Does anyone know of a way to do this for every permutation dynamically?

 

 

 

 

 

[corbin]

Hrmmm...  I guess it would go something like this:

 

 

 

In the set of numbers s, for each number n which is a number in the range 1 to x, the set of two numbers that will add to x is {1+y, x-y} where y is the position in the set s.

 

 

In other words, you will need to do something like:

 

 

$x = 1;
$y = 100;
$set = $first = $second = array();

for($i = 0; $i < $y; ++$i) {
    $first[] = $x + $i;
    $second[] = $x - $first[$i];
}

 

 

(That actually follows a bit different formula...  It just picks ascending first numbers and then picks the second based on the max - the current number.)

[.josh]

So basically you want to end up with 50 individual two element arrays? I don't really see why you would want to do that...I would suggest you have a single multi-dim array, like:

 

$array[0][0] = 1;

$array[0][1] = 99;

$array[1][0] = 2;

$array[1][1] = 98;

etc...

 

<?php
$a = range(1,50);
$b = range(99,50);
foreach($a as $k => $n) {
  $array[] = array($n,$b[$k]);
}
echo "<pre>";
print_r($array);

 

output:

Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 99
        )

    [1] => Array
        (
            [0] => 2
            [1] => 98
        )

    [2] => Array
        (
            [0] => 3
            [1] => 97
        )

    [3] => Array
        (
            [0] => 4
            [1] => 96
        )

    [4] => Array
        (
            [0] => 5
            [1] => 95
        )

etc...

 

[tallberg]

I want to end up with as many arrays are there are combinations of numbers that add up to 100 so i can use those number combinations as possible percentages.

 

array1 = array('1','99');

arrary2 = arrary('2','98');

 

skiping forward and im guessing the array number name

 

array33 = array('33','1', '60');

 

skipping forward again

 

array365 = array('9', '21', '3', '7', '60')

 

and so on untill there are all possible combinations of numbers that add up to 100

 

Thank for you help

 

[Mark Baker]

I'd assume by "numbers" that you mean "positive integers"

[tallberg]

I do.

[Daniel0]

so i can use those number combinations

 

Maybe you should elaborate on that. It sounds like there are better ways to do what you're trying to do.

[.josh]

Agreed.  I'm kind of curious as to what you really need here.  From what you are saying, you will end up with a massive amount of arrays.  I mean think about it:

 

95 + n = 100

n = 1 + 4

n = 1 + 3 + 1

n = 1 + 2 + 2

n = 1 + 2 + 1 + 1

n = 1 + 1 + 1 + 1 + 1

n = 2 + 3

n = 5

 

That's 7 arrays for the number 95.  7 ways to mix and match n adding up to 5.  Can you imagine how many different ways there are to mix and match numbers that add up to 50? Because the last combo will be 50 + 50 = 100.

[tallberg]

I imagine it is in the thousands.

 

The out put will be graphical making use of a 100% screen width and height.

This is why it involves the number 100

 

Im an artist as well as a part time web designer.

 

I think it could be very interesting to get the math right.

 

 

 

 

[Daniel0]

Yeah you already said that, but how and why? Say I give you the array you're looking for? How do you intend to use it?

[tallberg]

The result will be a random generated table with random colours for td cells.

Its part of a project involving a comparision between the craft and development of open sources technology and embroidery.

 

I want to split the table into random percentages for td but the ramdom numbers obviously have to be contrained by numbers that add up to 100. If you can do the math and the peice goes in the touring exhibition i could credit you as having done the math.

[.josh]

Okay so your overall goal here is to come up with a random set of numbers that add up to 100.  So, you don't need to necessarily calculate or use all of the permutations, you just need one of them? 

 

If that is the case, you can do this:

<?php
$num = 100;
while ($num >= 1) {
  $rN = rand(1,$num - 1);
  $d[] = $rN;
  $num -= $rN;
}
echo "<pre>";
print_r($d);
echo array_sum($d);

[Mark Baker]

$target = 100;

$total = 0;
$numbers = array();
while ($total < $target) {
$value = rand(0,$target-$total);
$numbers[] = $value;
$total += $value;
}

print_r($numbers);
echo '<br />'.array_sum($numbers);

[.josh]

lol mark I edited my post to put my code in, saw that you posted almost the exact same thing, except you add up insteda of subtract down.  One thing about yours though is that you include 0 in the range.  I don't know if this is something the OP would want. I mean, I guess technically 100 + 0 = 100, but dunno if he really wants that...I kind of assumed he would not want that one, so I did not account for it.  But anyways, it gives your code the side effect of randomly generating 0's. It still adds up to 100 and all, but you're gonna have to do something about multiple zeros showing up (or at all, unless it's 100 + 0). 

[Mark Baker]

One thing about yours though is that you include 0 in the range.

Easy enough to change.

 

The while loop can also be "simplified" to a single line as well, making it fractionally faster

while ($total < $target) {
$total += $numbers[] = rand(1,$target-$total);
}

[tallberg]

Thanks alot for this.

 

I just looking at the behavior of the script and one thing I notice is

there is not much chance for the number of numbers (count($numbers);  to go very high.

I would like the possibility for say 100 * 1 at the very extreme.

[Mark Baker]

I just looking at the behavior of the script and one thing I notice is there is not much chance for the number of numbers (count($numbers);  to go very high.

I would like the possibility for say 100 * 1 at the very extreme.

It is possible, just unlikely. The routine simply generates random numbers, with the range for each successive random number being limited by the sum of the preceding random numbers.

There's a 1:100 possibility of the first number generated being a 1, which would give a 1:99 possibility of the second number generated being a 1, a 1:98 possibility of the 3rd random number also being a 1, etc.

[.josh]

I think your overall math may be a bit off there... while that is true, the odds of you getting 100 1's are not the same as you getting 99 + 1

[Daniel0]

the odds of you getting 100 1's are not the same as you getting 99 + 1

 

Actually it is. If you generate an array of arrays of natural numbers whose sum is 100, when randomly selecting one of these arrays, the probability of selecting 99+1 is equal to the probability of 100*1. It's unlikely that you select either of those particular ones out of the many that exist, but they are equally probable.

 

Edit: Nevermind. I was still thinking about his initial way of solving the problem.

[Mark Baker]

I think your overall math may be a bit off there... while that is true, the odds of you getting 100 1's are not the same as you getting 99 + 1

My math might be wrong, but I calculate:

The odds of getting 99+1 is 1:100 * 1:1 => 1:100

The odds of getting 100 1's is 1:100 * 1:99 * 1:98 * 1:97.... * 1:1 => 1:9.3326E+157

 

[Third_Degree]

tallberg have you gotten your answer? If not, to address you're original question this is what you'd have to do.

 

You need to have a script that first generates all the combinations of two integers that equal 100, then all of the ones with 3 integers , then 4 integers, etc.. all the way up to 100 1's, with each having a different rule you would need to rationalize.  If order matters, you're in for a h*ll of a time.  If you understand my method, you'll also understand that anyone who did that for you would deserve some cash money and a medal.

[tallberg]

You are right in what you a say about what i want the script to do.

I cant say i have the code yet.

Order doesnt matter just all the combinations. A script i could write would chose one at random.

 

Im afriad there is no buddgest for the project just the glory of being credited in an exhibition that is traveling the world.

 

 

[Mark Baker]

function recurse(&$final,&$working,$target) {
if (array_sum($working) > $target) {
	array_pop($working);
} elseif (array_sum($working) == $target) {
	if (count($working) > 1) {
		$final[] = implode(',',$working);
	}
} else {
	$tmpTarget = $target - array_sum($working);
	for ($i = 1; $i <= $tmpTarget; $i++) {
		$working[] = $i;
		recurse($final,$working,$target);
		array_pop($working);
	}
}
}

$target = 100;
$final = $working = array();
recurse($final,$working,$target);
echo '<pre>';
print_r($final);
echo '</pre>';

Be warned. Disable any time limits, and whack memory up as high as you can make it.

[Mark Baker]

If it helps, there are 633,825,300,114,114,700,748,351,602,687 possible combinations

[.josh]

I think it would be easier for you to rig the previous code(s) posted.  Setup some extra conditions and random number generation to inflate the lower numbers coming up.  For example:

 

<?php
$num = 100;
while ($num >= 1) {
  $x = rand(1,2);
  if($x == 1) $num = ($num > 51) ? 51 : $num;

  $rN = rand(1,$num - 1);
  $d[] = $rN;
  $num -= $rN;
}
echo "<pre>";
print_r($d);
echo array_sum($d);

 

I have no idea what kind of odds that produces, but overall the idea is that 50 percent of the time it will cap the max range at 50 so the random numbers generated that add up to 100 will (ideally) half the time be generated as <= 50.    You could extend this or play with it; point is to rig it to get the lower numbers to come up more often. 

 

Only way to have an equal chance of any combination to show up though is, as mentioned by many, to generate all of them and then pick one at random, which IMO is not feasible.  Better to fake it/simulate it and approximation.