0

I’m aware of several questions covering this topic (e.g. here), but none of them (at least from what I found) do what I need.

Say I have an array of 3 elements [1, 2, 3]. I need to find all the possible unique combinations (so excluding permutations, like here), including the ones of repeating elements. So the result should be:

[1]
[2]
[3]
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 2, 3]
[1, 3, 3]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 3]

Excluding subsets like [3, 2, 1] or [2, 1, 3], that are the same thing as [1, 2, 3].

How can I achieve this?

Community
  • 1
  • 1
Alex
  • 5,565
  • 6
  • 36
  • 57
  • @JohnConde It’s not a duplicate, since it doesn’t cover the `AA, BB, CC, AAA, BBB, CCC` cases. – Alex Mar 25 '13 at 21:11
  • @Alex is there only 3 elements or will there be more elements ? – HamZa Mar 25 '13 at 21:18
  • 1
    Is `[1, 1, 1, 1, 1, 1, 1, 1, 1]` a "subset"? – Koterpillar Mar 25 '13 at 21:35
  • Of `[1, 2, 3]`? Can’t see how it could be. But it is a subset of `[1, 2, 3, 4, 5, 6, 7, 8, 9]`. – Alex Mar 25 '13 at 21:37
  • My math is fuzzy - are you asking for a powerset or is this slightly different? – Izkata Mar 25 '13 at 21:58
  • @Izkata a power set plus all the combinations that include similar elements, e.g. `[1,1]`, `[1,1,1]`, `[1,1,2]` and so on, so it’s slightly different. – Alex Mar 25 '13 at 22:01
  • The choice of the word `subset` is not accurate and is confusing people. I'd suggest looking for another term. – madth3 Mar 26 '13 at 02:24

1 Answers1

5

Fast solution using recursion, probably not the best way to do it, but it gets the job done.

<?php

$arr = array(1,2,3);
$result = array();

function combinations($arr, $level, &$result, $curr=array()) {
    for($i = 0; $i < count($arr); $i++) {
        $new = array_merge($curr, array($arr[$i]));
        if($level == 1) {
            sort($new);
            if (!in_array($new, $result)) {
                $result[] = $new;          
            }
        } else {
            combinations($arr, $level - 1, $result, $new);
        }
    }
}
for ($i = 0; $i<count($arr); $i++) {
    combinations($arr, $i+1, $result);
}

// TEST
foreach ($result as $arr) {
    echo join(" ", $arr) . '<br>';
}

?>
Aljana Polanc
  • 950
  • 8
  • 12