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>";
 ?>

• Allendar: 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.
• Wayne Links: @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
• Simon Forsberg: Do you only want the number $x as output, or the actual combinations themselves?
• Wayne Links: @SimonAndréForsberg I only want the number $x as output
• Simon Forsberg: 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?

Answer 1

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

• Wayne Links: 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: 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
• Shahid Karimi: Hey! This is not the solution. He is asking to print the three numbers

Answer 2

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>";
 }
}

• Wayne Links: 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.
• Simon Forsberg: 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.
• Shahid Karimi: What the hell 56 is here? @Edward Lee

Answer 3

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 :

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

and so on

• Radu Bogdan: PS, if you want duplicate numbers you can start the recursivity from the $i instead of $i+1 [generate($i, $solution);]