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.

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

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
)

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

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;
}

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
        )

)

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);

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)
  }
}

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)';