Find combination of array keys with values

Question

In order to optimize the output I recently ran into a situation where I have to get the all the combinations of array keys inside an array. I looked into several places (including StackOverflow) but could not find the solution since most are related to permutation rather than combination.

Given this input

$input = ['jack' => 11, 'moe' => 12, 'shane' => 12];

Output should be something like this (the order inside an array does not matter).

$output = [     
   ['jack'  => 11],
   ['jack'  => 11, 'moe' => 12]
   ['jack'  => 11, 'moe' => 12, 'shane' => 12]
   ['moe'   => 12],
   ['moe'   => 12, 'shane' => 12]
   ['shane' => 12],
   ['shane' => 12, 'jack' => 11]
];

I tried this but after third iteration it does not work.

function combination(array $inputs, array $temp, &$collect) {

    if (!empty($temp)) {

        $collect[] = $temp;
    }

    for ($i = 0; $i < sizeof($inputs); $i++) {

        $inputCopy = $inputs;

        $elem = array_splice($inputCopy, $i, 1); 

        if (count($inputCopy) > 0) {

            $temp[array_keys($elem)[0]] = array_values($elem)[0];

            combination($inputCopy, $temp, $collect);

        } else {

            $temp[array_keys($elem)[0]] = array_values($elem)[0];
            $collect[] = $temp;
            $temp = [];
        }

        $i++;

    }
}

Though I need this in PHP even Python (without using itertools combination), Java, Javascript will work for me.

Unex · Accepted Answer · 2016-12-01 17:25:28Z

2

I have found a way of doing what you want, but definitely, this is not a "fancy" solution. I would suggest you to work a little bit with it to find something better, but at least this gives you the result.

Here you go :

   <?php

    $baseArray = [
    "joe"   => 11,
    "molly" => 12,
    "sam"   => 13,
    ];

function getAllPermutations($array = []) {
    if (empty($array)) {
        return [];
    }

    $result = [];

    foreach ($array as $key => $value) {
        unset($array[$key]);
        $subPermutations = getAllPermutations($array);
        $result[] = [$key => $value];
        foreach ($subPermutations as $sub) {
            $result[] = array_merge([$key => $value] , $sub);
        }
    }
    return $result;
}

print_r(getAllPermutations($baseArray));

Output being :

Array
(
    [0] => Array
        (
            [joe] => 11
        )

    [1] => Array
        (
            [joe] => 11
            [molly] => 12
        )

    [2] => Array
        (
            [joe] => 11
            [molly] => 12
            [sam] => 13
        )

    [3] => Array
        (
            [joe] => 11
            [sam] => 13
        )

    [4] => Array
        (
            [molly] => 12
        )

    [5] => Array
        (
            [molly] => 12
            [sam] => 13
        )

    [6] => Array
        (
            [sam] => 13
        )

)    }

Hope this helped.

answered Dec 1, 2016 at 17:25

Unex

1,76713 silver badges17 bronze badges

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

3 Comments

nicholasnet Over a year ago

Thank you very much for your reply. But this solution did not work with input like this. ` $input = [123 => 0.3, 124 => 0.3, 125 => 0.6, 126 => 0.9]; In second iteration keys were all of.

nicholasnet Over a year ago

But it helped me too understand the problem better. Thank you very much.

nicholasnet Over a year ago

Actually only problem in your code was $result[] = array_merge([$key => $value] , $sub); should be $result[] = [$key => $value] + $sub; Rest was fine thank you.

sevavietl · Accepted Answer · 2016-12-01 20:41:50Z

1

You read about really clever non-recursive algorithm here: PHP: Find every combination of an Array. You can adopt it (mostly copy and paste) to write generator function:

function keyCombinations($array)
{
    $keys = array_keys($array);

    $num = count($keys); 
    $total = pow(2, $num);

    for ($i = 1; $i < $total; $i++) {
        $combination = [];
        for ($j = 0; $j < $num; $j++) {
            if (pow(2, $j) & $i) {
                $key = $keys[$j];

                $combination[$key] = $array[$key];
            }
        } 
        yield $combination;
    }
}

One important point here. In the original article $i initialized with 0, we initialize it with 1 to exclude empty array from the result.

Having this function you can get all combinations:

foreach (keyCombinations($input) as $combination) {
    print_r($combination);
}

Here is working demo.

answered Dec 1, 2016 at 20:41

sevavietl

3,7921 gold badge16 silver badges21 bronze badges

1 Comment

nicholasnet Over a year ago

I had to make some changes in your example but it worked. Thank you very much.

Tolokoban · Accepted Answer · 2016-12-01 17:15:54Z

0

If, in your final combination, you include the empty set, your problem is equivalent to enumerating a binary number of "n" bits. Where "n" is the number of elements in your set.

You need a recursive algorithm like this one:

def comb(initialSet, results=[], currentIndex=0, currentResult=[]):
    if currentIndex >= len(initialSet):
        results.append( currentResult[:] )
    else:
        currentResult.append( initialSet[currentIndex] )
        comb(initialSet, results, currentIndex + 1, currentResult)
        currentResult.pop()
        comb(initialSet, results, currentIndex + 1, currentResult)
    return results

answered Dec 1, 2016 at 17:15

Tolokoban

2,36916 silver badges18 bronze badges

Collectives™ on Stack Overflow

Find combination of array keys with values

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related