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
– nl-x, Commented May 21, 2013 at 8:05
sorry, wanted to give an answer. started in the wrong field. — Loek Bergman
– Loek Bergman, Commented May 21, 2013 at 8: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
– Loek Bergman, Commented May 21, 2013 at 8:21
@nl-x because sometimes the placeholder may be bigger than count($a) — user78431
– user78431, Commented May 21, 2013 at 9:16

Community · Accepted Answer · 2017-05-23 11:49:17Z

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, 2017 at 11:49

CommunityBot

11 silver badge

answered May 21, 2013 at 8:51

bitWorking

12.7k1 gold badge34 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 11:57:23Z

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

Collectives™ on Stack Overflow

PHP combinations of array elements

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related