Finding out combinations of x amount of integers to sum a given number

Question

I am trying to figure out how I can loop out possible combinations of a x amount of integers to sum a specifik number.

Let's say, I have number 7 and I need to figure out how I can sum that number with integers in pairs 3. 1+2+4 = 7

3+3+1 = 7

5+1+1 = 7

2+2+3 = 7

Repeated combinations of numbers doesn't interest me, e.g.:

1+2+4 = 7

2+4+1 = 7

4+2+1 = 7

Anyone got any ideas of how I should proceed to reach this result? Thanks.

This sounds like homework - have you tried *anything* yourself, or should we do everything for you? — h2ooooooo, Feb 19 '14 at 18:12
There are an infinite number of integer combinations that result in 7. For every X you could do `7 + X + (-X) = 7`. Are you perhaps looking for a combination of natural numbers? — Mureinik, Feb 19 '14 at 18:17
It's honestly not a homework problem, I assure you. The attempts I made were really no good, so I didn't post them. I now realize I should have. I never asked for a complete solution to this issue, just simply ideas of I should proceed :) — faerin, Feb 19 '14 at 18:40
http://cstaecker.fairfield.edu/~cstaecker/classwiki/index.php/Partitions_of_Integers_and_the_Partition_Function — Ashwin Parmar, Feb 19 '14 at 19:16

Nishant Solanki · Answer 1 · 2017-07-27T11:12:39.943

0

you can try this algorithm

$ans = array();
for($i=1;$i<=5;$i++)
{
    $i1 = 7-$i;
    $i2 = intval($i1 - $i);
    $value = $i."+".$i1."+".$i2;
    $ans = array_unshift($ans,$value);
}

print_r($ans);

hope this helps.. PLease let me know

edited Jul 27 '17 at 11:12

answered Feb 19 '14 at 18:25

Nishant Solanki

2,119
3
19
32

score 0 · Answer 2 · answered Feb 19 '14 at 20:01

0

Here is the solution for your problem.

function printPartitions($target, $max, $s){
    if($target === 0 )
        echo $s;
    else
        {
            if($max > 1)
            {
                printPartitions($target, $max-1, $s);
            }
            if($max <= $target)
            {
                printPartitions($target-$max, $max, $max . " " . $s);
            }
        }
}

printPartitions(5, 5, "<br/>");

You have to specify the $target Value, $max value.

e.g.

printPartitions(7, 7, "<br/>");

It will give you output like:

1 1 1 1 1 1 1 
1 1 1 1 1 2 
1 1 1 2 2 
1 2 2 2 
1 1 1 1 3 
1 1 2 3 
2 2 3 
1 3 3 
1 1 1 4 
1 2 4 
3 4 
1 1 5 
2 5 
1 6 
7

answered Feb 19 '14 at 20:01

Ashwin Parmar

3,025
3
26
42

Thank you so much for your effort, but it's still not do the right thing. Specifying number 7 as the my target and 3 as the max digit for integers to sum. So the results printed can never contain more (neither less) than 3 integers (2+4+1 = 7, 3+3+1 = 7) to sum the target. – faerin Feb 19 '14 at 20:20
Your should provide two options Target = Your Number Max = Your Number It will give you all possible sequences. – Ashwin Parmar Feb 20 '14 at 05:44
I'm sorry, but it doesn't give all possible sequences. Using your function like this printPartitions(7, 3, "
"); will output (I'll use brackets to seperate the lost line breaks here): [1 1 1 1 1 1 1] [1 1 1 1 1 2] [1 1 1 2 2] [1 2 2 2] [1 1 1 1 3] [1 1 2 3] [2 2 3] [1 3 3] Possible combinations also include the examples posted in my previous reply. By using number 3 as my max I meant using 3 integers to sum the target - not that 3 would be the highest number used to achieve this. Thanks for the effort, I appriciate it :) – faerin Feb 20 '14 at 13:35

score 0 · Accepted Answer · edited May 23 '17 at 12:10

I've got a solution to my problem. I feel I should defientely share it here, if anyone would ever need it. My solutions is based on this post: https://stackoverflow.com/a/19067884/3293843

<?php
function sampling($chars, $size, $combinations = array()) {
    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination .'@'. $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('1', '2', '3','4');
$target = 7;
$maxLengthOfIntegers = 3;
$output = sampling($chars, $maxLengthOfIntegers);
$repeatedEntries = array();


//presenting the output
foreach($output as $out){
    $explodeOut = explode('@',$out);
    sort($explodeOut);
    if(array_sum($explodeOut) == $target){
        $sortedPattern = implode('',$explodeOut);
        if(!in_array($sortedPattern,$repeatedEntries)){
            echo $sortedPattern.'<br/>';
            $repeatedEntries[] = $sortedPattern;
            }
        }
    }
?>

Thank you for your time and efforts.

Regards, Jacob

You have a bug in your script. The way your script looks and works it's designed to also allow combinations of two (like 3+4) or one number, not only three ($maxLengthOfIntegers). Yet, those combinations, though calculated get thrown away in every following loop. The last line of the function needs to be `return sampling($chars, $size - 1, array_merge($combinations, $new_combinations));` to keep the previous work. Note the array_merge() — fun2life, Jul 14 '21 at 15:17

Finding out combinations of x amount of integers to sum a given number

3 Answers3