PHP array combinations

Question

I have an array of 7 numbers (1,2,3,4,5,6,7) and I want to choose 5 of the numbers like
(1,2,3,4,5), (1,2,3,4,6), (1,2,3,4,7).
Note that (1,2,3,4,5) is equal to (4,5,3,1,2), so only one of those should be included in the output.

I would like to know if there is a function in PHP or any algorithm that can do this ? I have no idea where to start from. Can you help me ?

I want all the combinations of 7 given numbers ( they are taken from an array ) put into 5 slots, disregarding order.

Spiritual

Can you provide a little more spec? I am having a hard time abstracting it from the sample sets - provided it has been a decade since I took the SAT. – Kenzie

Do you want to generate all combinations of the numbers 1 to 7 put into 5 slots, disregarding order? – Hector

You want the subset of the elements, right? – Cathcart

@Hector - I want all the combinations of 7 given numbers ( they are taken from an array ) put into 5 slots,disregarding order – Spiritual

Answer 1

You can use the solution found here http://stereofrog.com/blok/on/070910.

Incase the link goes down here's the code....

class Combinations implements Iterator
{
    protected $c = null;
    protected $s = null;
    protected $n = 0;
    protected $k = 0;
    protected $pos = 0;

    function __construct($s, $k) {
        if(is_array($s)) {
            $this->s = array_values($s);
            $this->n = count($this->s);
        } else {
            $this->s = (string) $s;
            $this->n = strlen($this->s);
        }
        $this->k = $k;
        $this->rewind();
    }
    function key() {
        return $this->pos;
    }
    function current() {
        $r = array();
        for($i = 0; $i < $this->k; $i++)
            $r[] = $this->s[$this->c[$i]];
        return is_array($this->s) ? $r : implode('', $r);
    }
    function next() {
        if($this->_next())
            $this->pos++;
        else
            $this->pos = -1;
    }
    function rewind() {
        $this->c = range(0, $this->k);
        $this->pos = 0;
    }
    function valid() {
        return $this->pos >= 0;
    }

    protected function _next() {
        $i = $this->k - 1;
        while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
            $i--;
        if($i < 0)
            return false;
        $this->c[$i]++;
        while($i++ < $this->k - 1)
            $this->c[$i] = $this->c[$i - 1] + 1;
        return true;
    }
}


foreach(new Combinations("1234567", 5) as $substring)
    echo $substring, ' ';

12345 12346 12347 12356 12357 12367 12456 12457 12467 12567 13456 13457 13467 13567 14567 23456 23457 23467 23567 24567 34567

Softwood

Thanks for posting this here as the link appears to be dead now :) – Rush

this is fine with range array(1, 2, 3, 4, 5, 6, 7) but for suppose if range is 1-80 ?? i am getting Out of memory (allocated 1837629440) – Dogoodism

@Dogoodism The count of combinations grows like a factorial, which is even faster than an exponential. For 50 elements, C(50,25) = 50!/(25! x 25!) = 126,410,606,437,752. Assuming generating the sequences costs nothing and you can process any given sequence in 1µs (one million sequences per second), you would need about four years to process C(50,25) sequences. Using a generator might avoid the memory issue, but you wouldn't have enough CPU to do anything useful with the result anyway. – Teachin

Answer 2

<?php

echo "<pre>";
$test = array("test_1","test_2","test_3");

// Get Combination
$return = uniqueCombination($test);

//Sort
sort($return);

//Pretty Print
print_r(array_map(function($v){ return implode(",", $v); }, $return));

function uniqueCombination($in, $minLength = 1, $max = 2000) {
    $count = count($in);
    $members = pow(2, $count);
    $return = array();
    for($i = 0; $i < $members; $i ++) {
        $b = sprintf("%0" . $count . "b", $i);
        $out = array();
        for($j = 0; $j < $count; $j ++) {
            $b{$j} == '1' and $out[] = $in[$j];
        }

        count($out) >= $minLength && count($out) <= $max and $return[] = $out;
        }
    return $return;
}

?>

output

Array
(
    [0] => test_1
    [1] => test_2
    [2] => test_3
    [3] => test_1,test_2
    [4] => test_1,test_3
    [5] => test_2,test_3
    [6] => test_1,test_2,test_3
)

Engender

Welcome to Stack Overflow! Although this code may help to solve the problem, it doesn't explain why and/or how it answers the question. Providing this additional context would significantly improve its long-term value. Please edit your answer to add explanation, including what limitations and assumptions apply. – Sharonsharona

and mine as well! But explanations of how it works would really help!... Especially those sprintf() and and usages – Lobachevsky

this is fine with range array(1, 2, 3, 4, 5, 6, 7) but for suppose if range is 1-80 ?? i am getting Out of memory (allocated 1837629440) – Dogoodism

Answer 3

The Math_Combinatorics in PEAR repository does exactly what you want:

A package that returns all the combinations and permutations, without repetition, of a given set and subset size. Associative arrays are preserved.

require_once 'Math/Combinatorics.php';
$combinatorics = new Math_Combinatorics;

$input = array(1, 2, 3, 4, 5, 6, 7);
$output = $combinatorics->combinations($input, 5); // 5 is the subset size

// 1,2,3,4,5
// 1,2,3,4,6
// 1,2,3,4,7
// 1,2,3,5,6
// 1,2,3,5,7
// 1,2,3,6,7
// 1,2,4,5,6
// 1,2,4,5,7
// 1,2,4,6,7
// 1,2,5,6,7
// 1,3,4,5,6
// 1,3,4,5,7
// 1,3,4,6,7
// 1,3,5,6,7
// 1,4,5,6,7
// 2,3,4,5,6
// 2,3,4,5,7
// 2,3,4,6,7
// 2,3,5,6,7
// 2,4,5,6,7
// 3,4,5,6,7

Schiro

this is fine with range array(1, 2, 3, 4, 5, 6, 7) but for suppose if range is 1-80 ?? i am getting Out of memory (allocated 1837629440) – Dogoodism

80 items taken 5 at a time results in 24,040,016 combinations. That is too many! – Schiro

yes Salman, its true, but i needed, its working with 50 items, is there any solution to get this? – Dogoodism

Answer 4

Another solution that bases on stack. It's quit fast but eats much memory.

Hope that helps someone.

In detail:

function _combine($numbers, $length)
{
    $combinations = array();
    $stack = array();

    // every combinations can be ordered
    sort($numbers);

    // startup
    array_push($stack, array(
        'store' => array(),
        'options' => $numbers,
    ));

    while (true) {
        // pop a item
        $item = array_pop($stack);

        // end of stack
        if (!$item) {
            break;
        }

        // valid store
        if ($length <= count($item['store'])) {
            $combinations[] = $item['store'];
            continue;
        }

        // bypass when options are not enough
        if (count($item['store']) + count($item['options']) < $length) {
            continue;
        }

        foreach ($item['options'] as $index => $n) {
            $newStore = $item['store'];
            $newStore[] = $n;

            // every combine can be ordered
            // so accept only options which is greater than store numbers
            $newOptions = array_slice($item['options'], $index + 1);

            // push new items
            array_push($stack, array(
                'store' => $newStore,
                'options' => $newOptions,
            ));
        }
    }

    return $combinations;
}

Epigone

Answer 5

Improved this answer to work with associative array as well:

function uniqueCombination($values, $minLength = 1, $maxLength = 2000) {
    $count = count($values);
    $size = pow(2, $count);
    $keys = array_keys($values);
    $return = [];

    for($i = 0; $i < $size; $i ++) {
        $b = sprintf("%0" . $count . "b", $i);
        $out = [];

        for($j = 0; $j < $count; $j ++) {
            if ($b[$j] == '1') {
                $out[$keys[$j]] = $values[$keys[$j]];
            }
        }

        if (count($out) >= $minLength && count($out) <= $maxLength) {
             $return[] = $out;
        }
    }

    return $return;
}

Eg:

print_r(uniqueCombination([
    'a' => 'xyz',
    'b' => 'pqr',
]);

Result:

Array
(
    [0] => Array
        (
            [b] => pqr
        )

    [1] => Array
        (
            [a] => xyz
        )

    [2] => Array
        (
            [a] => xyz
            [b] => pqr
        )

)

It will still work for non-associative arrays:

print_r(uniqueCombination(['a', 'b']);

Result:

Array
(
    [0] => Array
        (
            [1] => b
        )

    [1] => Array
        (
            [0] => a
        )

    [2] => Array
        (
            [0] => a
            [1] => b
        )

)

Cormophyte

This works great for 10 items, but if I do it for 100 = no memory error – Sarabia

Answer 6

New solution which optimizes speed and memory for combining algorithm

Mindset: generate combinations K numbers of Array of numbers. New solution will use K 'for' statements. One 'for' One number. Such as: $K = 5 mean that 5 of 'for' statements is used

$total = count($array);
$i0 = -1;
for ($i1 = $i0 + 1; $i1 < $total; $i1++) {
    for ($i2 = $i1 + 1; $i2 < $total; $i2++) {
        for ($i3 = $i2 + 1; $i3 < $total; $i3++) {
            for ($i4 = $i3 + 1; $i4 < $total; $i4++) {
                for ($i5 = $i4 + 1; $i5 < $total; $i5++) {
                    $record = array();
                    for ($i = 1; $i <= $k; $i++) {
                        $t = "i$i";
                        $record[] = $array[$$t];
                    }
                    $callback($record);
                }
            }
        }
    }
}

And detail of code that generated the real code that will be execute by eval() function

function combine($array, $k, $callback)
{
    $total = count($array);
    $init = '
        $i0 = -1;
    ';
    $sample = '
        for($i{current} = $i{previous} + 1; $i{current} < $total; $i{current}++ ) {
            {body}
        }
    ';

    $do = '
        $record = array();
        for ($i = 1; $i <= $k; $i++) {
            $t = "i$i";
            $record[] = $array[$$t];
        }
        $callback($record);
    ';
    $for = '';
    for ($i = $k; $i >= 1; $i--) {
        switch ($i) {
            case $k:
                $for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $do], $sample);
                break;
            case 1:
                $for = $init . str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);
                break;
            default:
                $for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);
                break;
        }
    }

    // execute
    eval($for);
}

How to combine K numbers of Array

$k = 5;
$array = array(1, 2, 3, 4, 5, 6, 7);
$callback = function ($record) {
    echo implode($record) . "\n";
};
combine($array, $k, $callback);

Epigone

Answer 7

I found the other answers here confusing or overly complicated, so I wrote my own. I think this is a simple solution with a recursive method. The basic idea is that you go through your array and for each item decide whether or not it is in the combination (actually, you don't decide, you recursively try both ways). You make this choice for the first item and then combine it with the recursively generated combinations of the rest of the array. This solution fills a result array with every combination of your array as a sub-array. It uses the items in order and it preserves associations, including with numeric keys.

function combinations(array $items, int $numToChoose, array &$results, $comb = []): void {
  if (count($items) < $numToChoose) {
    throw new \Exception("Asked to choose $numToChoose items from an array of length ". count($items));
  }

  // if nothing left to choose, we have a complete combination
  if ($numToChoose === 0) {
    $results[] = $comb;
    return;
  }

  // if we have to choose everything at this point, then we know what to do
  if (count($items) == $numToChoose) {
    $results[] = $comb + $items;
    return;
  }

  // The recursive cases: either use the first element or not and find combinations of the rest
  $val = reset($items);
  $key = key($items);
  unset($items[$key]);

  // not using it
  combinations($items, $numToChoose, $results, $comb);

  // using it
  $comb[$key] = $val;
  combinations($items, $numToChoose - 1, $results, $comb);
}

// Do a test run
$combs = [];
combinations([1=>1, 2=>2, 3=>3], 2, $combs);
var_dump($perms);

This results in the output:

array(3) {
  [0]=>
  array(2) {
    [2]=>
    int(2)
    [3]=>
    int(3)
  }
  [1]=>
  array(2) {
    [1]=>
    int(1)
    [3]=>
    int(3)
  }
  [2]=>
  array(2) {
    [1]=>
    int(1)
    [2]=>
    int(2)
  }
}

Yirinec

Do you want array_key_first() instead of reset() then key()? – Rodmann

@mickmackusa, yeah, that would work too. Of course, I do want the value also, so I'd have to use that key to access the value, still two lines of code. Seems pretty equivalent to me. But, thanks for pointing out array_key_first, didn't have that method top of mind and could definitely help in some circumstances. – Yirinec

Answer 8

I needed a combining function that included subsets, so I took @Nguyen Van Vinh's answer and modified it for my needs.

If you pass [1,2,3,4] to the function, it returns every unique combination and subset, sorted:

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

Here's the function:

function get_combinations_with_length( $numbers, $length ){
    $result = array();
    $stack = array();
    // every combinations can be ordered
    sort($numbers);
    // startup
    array_push($stack, array(
        'store' => array(),
        'options' => $numbers,
    ));
    while (true) {
        // pop a item
        $item = array_pop($stack);
        // end of stack
        if (!$item) break;
        // valid store
        if ($length <= count($item['store'])) {
            $result[] = $item['store'];
            continue;
        }
        // bypass when options are not enough
        if (count($item['store']) + count($item['options']) < $length) {
            continue;
        }
        foreach ($item['options'] as $i=>$n) {
            $newStore = $item['store'];
            $newStore[] = $n;
            // every combine can be ordered, so accept only options that are greater than store numbers
            $newOptions = array_slice($item['options'], $i + 1);
            // array_unshift to sort numerically, array_push to reverse
            array_unshift($stack, array(
                'store' => $newStore,
                'options' => $newOptions,
            ));
        }
    }
    return $result;
}

function get_all_combinations( $numbers ){
    $length = count($numbers);
    $result = [];
    while ($length > 0) {
        $result = array_merge($result, get_combinations_with_length( $numbers, $length ));
        $length--;
    }
    return $result;
}


$numbers = [1,2,3,4];
$result = get_all_combinations($numbers);

echo 'START: '.json_encode( $numbers ).'<br><br>';
echo 'RESULT: '.json_encode( $result ).'<br><br>';
echo '('.count($result).' combination subsets found)';

Scallion