PHP combinations of array elements

Question

I want to generate all possible combination of array elements to fill a placeholder, the placeholder size could vary.

Let say I have array $a = array(3, 2, 9, 7) and placeholder size is 6. I want to generate something like the following:

3,3,3,3,3,3
2,3,3,3,3,3
2,2,3,3,3,3
...........
...........
7,7,7,7,7,9
7,7,7,7,7,7

However (2,3,3,3,3,3) would be considered the same as (3,2,3,3,3,3) so the later one doesn't count.

Could anyone point me to the right direction? I know there is Math_Combinatorics pear package, but that one is only applicable to placeholder size <= count($a).

Edit I am thinking that this one is similar to bits string combination though with different number base

This is not quite logical, as for some combinations are arbitrary. It would depend on the preceding combinations to make out whether a new combination is legal or not. Though still doable off course. — nl-x, May 21 '13 at 08:05
sorry, wanted to give an answer. started in the wrong field. — Loek Bergman, May 21 '13 at 08:07
@OfirBaruch: I knew it is. It will take too much time indeed. Will not give an answer. Sorry, haven't got that much time. — Loek Bergman, May 21 '13 at 08:21
@nl-x because sometimes the placeholder may be bigger than `count($a)` — user78431, May 21 '13 at 09:16
@user78431 that is not my question. I asked can placeholder be smaller than count($a) ? — nl-x, May 21 '13 at 09:17
For me to give you a working example. Your request requires elaborate programming. It is a nice puzzle, but not during day time hours while working. — Loek Bergman, May 21 '13 at 09:22
Take a look on elementary algorithm as you can see in http://rosettacode.org/wiki/Permutations_by_swapping — Mihai8, May 21 '13 at 13:01

score 1 · Answer 1 · edited May 23 '17 at 11:49

1

I have no PHP source code for you but some sources that might help.

Some C code. Look at 2.1: http://www.aconnect.de/friends/editions/computer/combinatoricode_g.html

Delphi code: combination without repetition of N elements without use for..to..do

Wiki article here

edited May 23 '17 at 11:49

Community

1
1

answered May 21 '13 at 08:51

bitWorking

12,485
1
32
38

score 0 · Answer 2 · edited May 23 '17 at 11:57

Well it took quit some time to figure this one out.

So i split the question into multiple parts

1. I firsrt made an array with all the possible value options.

function create_all_array($placeholder, array $values)
{
    if ($placeholder <= 0) {
        return [];
    }

    $stack = [];
    $values = array_unique($values);

    foreach ($values as $value) {
        $stack[] = [
            'first' => $value,
            'childs' => create_all_array($placeholder - 1, $values)
        ];
    }

    return $stack;
}

2. Then I made a function to stransform this massive amount of data into string (no check for uniques).

function string($values, $prefix = '')
{
    $stack = [];

    foreach($values as $value) {
        $sub_prefix = $prefix . $value['first'];

        if (empty($value['childs'])) {
            $stack[$sub_prefix] = (int)$sub_prefix;
        } else {
            $stack = array_merge($stack, string($value['childs'], $sub_prefix));
        }
    }

    return $stack;
}

3. Then the hard part came. Check for duplicates. This was harder than expected, but found some good anser to it and refactored it for my use.

function has_duplicate($string, $items)
{
    $explode = str_split ($string);
    foreach($items as $item) {
        $item_explode = str_split($item);

        sort($explode);
        $string = implode('',$explode);
        sort($item_explode);
        $item = implode($item_explode);

        if ($string == $item) {
            return true;
        }
    }

    return false;
}

4. The last step was to combine the intel into a new funciton :P

function unique_string($placeholder, array $values)
{
    $stack = string(create_all_array($placeholder, $values));

    $check_stack = [];
    foreach($stack as $key => $item) {
        if (has_duplicate($item, $check_stack)) {
            unset($stack[$key]);
        }
        $check_stack[] = $item;
    }
    return $stack;
}

Now you can use it simple as followed

unique_string(3 /* amount of dept */, [1,2,3] /* keys */);

Ps the code is based for PHP5.4+, to convert to lower you need to change the [] to array() but I love the new syntax so sorry :P

PHP combinations of array elements

2 Answers2