Get all possible combinations without duplicates

Question

How can I get all the possible combinations of given numbers. For instance I have

$arr = [ 1, 2, 3, 4]

I want to get the combinations without any duplicates inside the combinations

[1] => [1]
[2] => [2]
[3] => [3]
[4] => [4]
[5] => [1, 2]
[6] => [1, 3]
[7] => [1, 4]
[8] => [2, 3]
[9] => [2, 4]
[10] => [3, 4]
[11] => [1, 2, 3]
[12] => [1, 2, 4]
[13] => [1, 3, 4]
[14] => [2, 3, 4]
[15] => [1, 2, 3, 4]

Why is your example stopping by `1,2,3,4` your logic says that also `2,1,3,4` is right? — JustOnUnderMillions, Apr 28 '17 at 10:08
Do you mean "How do I write a script that will take these inputs and produce this output"? Otherwise, you have answered your own question. I would use nested loops and in each pass, try this `in_array` function - http://php.net/manual/en/function.in-array.php — Shaun Bebbers, Apr 28 '17 at 10:10
@JustOnUnderMillions `1, 2, 3, 4` is the same as `2, 1, 3, 4` so it's a duplicate — Enthys, Apr 28 '17 at 10:10
And `[2, 4]` is then equal to `[4, 2]` (both in example), plz be very clear on a question like that!? And try some and show that here ;-) — JustOnUnderMillions, Apr 28 '17 at 10:11
A combination without duplicates is a permutation. Have you tried calculating the permutations? — J. Michael Wuerth, Apr 28 '17 at 13:45

score 4 · Accepted Answer · answered Apr 28 '17 at 10:18

I hope below function work as per your expected output :

function get_array_combination($arr) {
    $results = array(array( ));

    foreach ($arr as $values)
        foreach ($results as $combination)
                array_push($results, array_merge($combination, array($values))); // Get new values and merge to your previous combination. And push it to your results array
    return $results;
}
$set = array('1', '2', '3', '4');
$final_array = get_array_combination($set);
echo "<pre>";
print_r(array_values(array_filter($final_array))); // Removed blank entry from array and re indexing array keys.

score 0 · Answer 2 · answered Oct 07 '20 at 20:42

I didn't like that the given solution is modifying an iterated variable within its loop and also I wanted a solution that I can easily understand to port to other languages. So here:

<?php
function permutation(array $arr)
{
        $out=[[]];
    
        foreach($arr as $key2=> $item2){
            $copy=$out;
            foreach($copy as $k=> $v){
                array_push($copy[$k],$item2 );
            }
            array_push($out,...$copy);
            
        }
        
        return $out;
}
print_r(permutation(array(1,2,3,4)));

This second one is intentionally weird to make it better to understand what is going on.

<?php
function permutation(array $arr)
{
    
    $out=[];
    
    while(count($arr)){
        
        $out_temp=[[]];
    
        foreach($arr as $key2=> $item2){
            $copy=$out_temp;
            foreach($copy as $k=> $v){
                array_push($copy[$k],$item2 );
            }
            if($key2==0){
                unset($out_temp[0]);
            }
            array_push($out_temp,...$copy);
 
        }
        
        array_push($out,...$out_temp);
        array_shift($arr);
    }

    return $out;
}
print_r(permutation(array(1,2,3,4,5)));

Get all possible combinations without duplicates

2 Answers2

Linked