Finding combinations of 3 numbers

Question

What this code tries to do is find possible combinations of three numbers. For example, let's say I have the following numbers:

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

Some possible combinations of three numbers would be:

1,2,3 
1,2,4 
2,3,4
2,3,5
2,3,6

I do get the desired outcome but my code looks ugly. Are there any remarks or alternate ways to do this?

<?php

    $numbers = [2, 8, 16, 30, 44, 48];
    $number  = $numbers;
    $slice   = [];
    $threes  = [];
    $x       = 1;
    $stake   = 10;
    $odds    = 325;

    echo implode(" | ", $numbers)."<br>";

    foreach ($numbers as $key) {

        if (count($number) == 6) {
            // $slice = array_slice($number, 0,3);

            $threes[] = $key;
            $threes[] .= next($number);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            //--------------------------------------------------------------//

            array_pop($threes);
            array_pop($threes);
            $threes[] .= prev($number);
            array_pop($threes);
            $threes[] .= prev($number);
            array_pop($threes);
            $threes[] .= prev($number);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            array_pop($threes);
            $threes[] = prev($number);
            array_pop($threes);
            $threes[] = prev($number);
            $threes[] = next($number);

            $x++;

            array_pop($threes);
            $threes[] = next($number);

            $x++;

            array_pop($threes);
            array_pop($threes);
            $threes[] = prev($number);
            $threes[] = next($number);

            $x++;

        } elseif (count($number) == 5) {
            $threes[] = $key;
            $threes[] .= next($number);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            array_pop($threes);
            $threes[] .= prev($number);
            array_pop($threes);
            $threes[] .= prev($number);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            array_pop($threes);
            $threes[] .= prev($number);
            $threes[] .= next($number);

            $x++;
        } elseif (count($number) == 4) {
            $threes[] = $key;
            $threes[] .= next($number);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            $threes[] .= next($number);

            $x++;

            array_pop($threes);
            array_pop($threes);
            $threes[] .= prev($number);
            $threes[] .= next($number);

            $x++;
        } elseif (count($number) == 3) {
            $threes[] = $key;
            $threes[] .= next($number);
            $threes[] .= next($number);

        }

        array_shift($number);
        $threes = [];
    }



    echo "<br>---------------------------------------------------------------------------<br>";
    echo "Total combinations of 3's: ".$x."<br>";

    ?>

These kind of problems require you to write smart recursive loops that will go until it depletes all possibilities. As you noticed yourself, it's undoable with flexible data to write all cases. — Allendar, Sep 5, 2014 at 21:50
@Allendar i agree, i have not really looked into recursive loops really. Yes it is undoable to write all cases but surely there should be a shorter way that i can write this. This code does seem long and tedious especially for what it tries to achieve — Wayne Links, Sep 5, 2014 at 21:55
Do you only want the number $x as output, or the actual combinations themselves? — Simon Forsberg, Sep 5, 2014 at 23:42
So I posted an answer, but it feels so strange to me that you have all this code that you don't end up using. What is the real purpose of the $numbers array? Why are you storing things in the $threes and emptying that array after each iteration? — Simon Forsberg, Sep 6, 2014 at 0:20

Community · Accepted Answer · 2020-06-10 13:24:26Z

Your current code

After a long investigation of the problem, I ended up solving more than what you are asking for. I totally misunderstood what your code were actually doing. I found out that your $numbers array is not interesting at all.

The output of your code, the variable $x is the Binomial coefficient for 6 choose 3. (Which is quite funny because in your question you asked about 7 numbers, but in your code you are using 6).

Your code is doing a whole lot of array_pop, next and prev which is just ugly. You need to spend more time thinking about what the algorithm is behind all of this.

Additionally, I don't know what you are intending to do with these lines:

$threes[] .= next($number);

Why use .= ? Last time I checked, .= is for string concatenation. What does that have to do with anything? And why do that when you add a new index to the array? That code does exactly the same as $threes[] = next($number);

You seem to add a whole lot of stuff to the $threes array, but you never end up using it.

Additionally, your $stake, $odds and even $slice seem totally irrelevant here.

Shortening your code

When removing everything related to $threes, and simplifying your multiple $x++ to one $x += ...; your code can be dramatically shortened:

<?php

    $numbers = [2, 8, 16, 30, 44, 48];
    $number  = $numbers;
    $x       = 1;
    echo implode(" | ", $numbers)."<br>";

    foreach ($numbers as $key) {

        if (count($number) == 6) {
            $x += 10;
        } elseif (count($number) == 5) {
            $x += 6;
        } elseif (count($number) == 4) {
            $x += 3;
        } elseif (count($number) == 3) {
        }
        array_shift($number);
    }

    echo "Total combinations of 3's: ".$x."<br>";

?>

Then, when removing some more fluff and using an integer variable instead of that $numbers array.

<?php

    $number = 4;
    $x       = 1;
    for ($i = $number; $i >= 0; $i--) {
        if ($i == 6) {
            $x += 10;
        } elseif ($i == 5) {
            $x += 6;
        } elseif ($i == 4) {
            $x += 3;
        }
    }

    echo "Total combinations of 3's: ".$x."<br>";

?>

So, your code is not very extensible in it's current form. It can only support 3's and a maximum $number of 6... That's not optimal.

A better approach

This is how I calculate the Binomial coefficient in Java - which is in use in my Minesweeper Flags Extreme project, translated into PHP

function nCr($n, $r) {
    if (($r > $n) || ($r < 0)) {
        return 0;
    }
    if (($r == 0) || ($r == $n)) {
        return 1;
    }
    
    $value = 1;
    
    for ($i = 0; $i < $r; $i++) {
        $value = $value * ($n - $i) / ($r - $i);
    }
    
    return $value;
}

echo nCr(8, 4); // Prints 70
echo nCr(6, 3); // Your code example, prints 20

It is very tempting to write $value *= ..., but avoid doing that as the results will not be the same in languages which separates integer division and floating division (not that PHP is one of those languages, but I would still recommend avoiding it).

I agree my code is ugly as hell. The $stakes $odds $slice excerpt should have been removed hence the no relevancy. Thanks for the link to Minesweeper Flags Extreme project, it really gives some good insight. Thanks for taking the time. I like the way you reason or explain things, much appreciated — Wayne Links, Sep 6, 2014 at 0:21
Strangely enough, refering to your comment your code is not very extensible in it's current form. It can only support 3's and a maximum $number of 6... That's not optimal, when i saw your version that was the first thought that came to my mind how extensible your code is. I should really wrap my head around reusability — Wayne Links, Sep 6, 2014 at 0:25
Hey! This is not the solution. He is asking to print the three numbers — Shahid Karimi, Dec 13, 2017 at 10:48

Edward Lee · Accepted Answer · 2014-09-05 22:33:45Z

3

Yes, recursive loops are good solution for this question.

By the way,how about my solution? I used binary numbers to represent subsets.

for example,

000001 = 48
000010 = 40
000011 = 40, 48
.
.
.
000111 = 30, 44, 48
.
.
.
111111 = 2, 8, 16, 30, 44, 48

Find all binary numbers between 000111(least binary number contains 3 numbers) and 111000(greatest binary number contains 3 numbers).

And then filter binary numbers which contain three '1' and use their position as index of numbers array.

<?php

$numbers = [2, 8, 16, 30, 44, 48];
for ($i = 56; $i > 6; $i--) {
    $binary = sprintf("%06d", decbin($i));
    $count = substr_count($binary, '1');
    if ($count == 3) {
        for ($j = 0; $j < 3; $j++) {
            $lastpos = strpos($binary, '1');
            $binary[$lastpos] = 0;
            echo $numbers[$lastpos].' ';
        }
        echo "<br>";
    }
}

answered Sep 5, 2014 at 22:33

Edward Lee

1311 bronze badge

\$\begingroup\$ in this case it does work perfectly, i must say ive never thought about using binary numbers as subsets before! Very interesting, it is actually an eye opener. \$\endgroup\$
– Wayne Links
Sep 5, 2014 at 22:48
\$\begingroup\$ Your approach is not very optimal, complexity-wise. Also, "recursive loops are good solution for this question.", there is nothing recursive about the original solution. It is a loop, yes, but it is not recursive. \$\endgroup\$
– Simon Forsberg
Sep 7, 2014 at 18:29
\$\begingroup\$ What the hell 56 is here? @Edward Lee \$\endgroup\$
– Shahid Karimi
Dec 13, 2017 at 10:40

Add a comment |

Radu Bogdan · Accepted Answer · 2014-09-05 22:02:55Z

A more easier way to this is is using recursivity

<?php
$numbers = array(
    2,
    8,
    16,
    30,
    44,
    48
);

$solutions = array();

function generate($k, $solution)
{
    global $solutions, $numbers;
    if (count($solution) == 3) {
        $solutions[] = $solution;
    }
    if (count($solution) < 3)
        for ($i = $k; $i < count($numbers); $i++) {
            $solution[] = $numbers[$i];
            generate($i + 1, $solution);
            array_pop($solution);
        }

}

generate(0, array());

echo "<P>Total number of combinations:" . count($solutions) . "</p>";
echo "<p> solutions: </p>";
foreach ($solutions as $sol) {
    echo "<p> {$sol[0]} {$sol[1]} {$sol[2]} </p>";
}
?>

It works like this:

You build your solution into the $solution variable, when it has 3 elements you add it to the array of $solutions

So it does something like add this :

first call add first element -> re-call
second call add second element -> re-call
third call add third element -> re-call
solution length = 3 add it to solutions return to the last call ( third call)
third call , last added element is removed, next one is added

and so on

PS, if you want duplicate numbers you can start the recursivity from the $i instead of $i+1 [generate($i, $solution);] — Radu Bogdan, Sep 5, 2014 at 22:05

Stack Exchange Network

Finding combinations of 3 numbers

3 Answers 3

Your current code

Shortening your code

A better approach

Your Answer

Not the answer you're looking for? Browse other questions tagged
php
php5
combinatorics
or ask your own question.

Linked

Hot Network Questions

Finding combinations of 3 numbers

3 Answers 3

Your current code

Shortening your code

A better approach

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged phpphp5combinatorics or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
php
php5
combinatorics
or ask your own question.