All combinations of r elements from given array ph

Question

Given an array such as the following

$array = ('1', '2', '3', '4', '5', '6', '7');

I'm looking for a method to generate all possible combinations, with a minimum number of elements required in each combination r. (eg if r = 5 then it will return all possible combinations containing at least 5 elements)

Answer 1

A combination can be expressed as

ⁿC_r = n! / (r! - (n - r)!)

First, we determine $n as the number of elements in the array. And $r is the minimum number of elements in each combination.

$a = ['1', '2', '3', '4', '5', '6', '7'];  // the array of elements we are interested in

// Determine the `n` and `r` in nCr = n! / (r! * (n-r)!)
$r = 5;
$n = count($a);

Next, we determine $max as the maximum number that can be represented by $n binary digits. That is, if $n = 3, then $max = (111)₂ = 7. To do this, we first create a empty string $maxBinary and add $n number of 1s to it. We then convert it to decimal, and store it in $max.

$maxBinary = "";
for ($i = 0; $i < $n; $i++)
{
  $maxBinary .= "1";
}
$max = bindec($maxBinary);  // convert it into a decimal value, so that we can use it in the following for loop

Then, we list out every binary number from 0 to $max and store those that have more than $r number of 1s in them.

$allBinary = array();  // the array of binary numbers
for ($i = 0; $i <= $max; $i++)
{
  if (substr_count(decbin($i), "1") >= $r)  // we count the number of ones to determine if they are >= $r
  {
    // we make the length of the binary numbers equal to the number of elements in the array,
    // so that it is easy to select elements from the array, based on which of the digits are 1.
    // we do this by padding zeros to the left.
    $temp = str_pad(decbin($i), $n, "0", STR_PAD_LEFT);
    $allBinary[] = $temp;
  }
}

Then, we use the same trick as above to select elements for our combination. I believe the comments explain enough.

$combs = array();  // the array for all the combinations.
$row = array();    // the array of binary digits in one element of the $allBinary array.

foreach ($allBinary as $key => $one)
{
  $combs[$key] = "";
  $row = str_split($one);  // we store the digits of the binary number individually
  foreach ($row as $indx => $digit)
  {
    if ($digit == '1')  // if the digit is 1, then the corresponding element in the array is part of this combination.
    {
      $combs[$key] .= $a[$indx];  // add the array element at the corresponding index to the combination
    }
  }
}

And that is it. You are done!

Now if you have something like

echo count($combs);

then it would give you 29.

Additional notes:

I read up on this only after seeing your question, and as a newcomer, I found these useful:

• Wikipedia - http://en.wikipedia.org/wiki/Combination
• Php recursion to get all possibilities of strings
• Algorithm to return all combinations of k elements from n

Also, here are some quick links to the docs, that should help people who see this in the future:

• http://php.net/manual/en/function.decbin.php
• http://php.net/manual/en/function.bindec.php
• http://php.net/manual/en/function.str-pad.php

Answer 2

Combinations of k out of n items can be defined recursively using the following function:

function combinationsOf($k, $xs){
        if ($k === 0)
            return array(array());
        if (count($xs) === 0)
            return array();
        $x = $xs[0];
        $xs1 = array_slice($xs,1,count($xs)-1);
        $res1 = combinationsOf($k-1,$xs1);
        for ($i = 0; $i < count($res1); $i++) {
            array_splice($res1[$i], 0, 0, $x);
        }
        $res2 = combinationsOf($k,$xs1);
        return array_merge($res1, $res2);
    }

The above is based on the recursive definition that to choose k out n elements, one can fix an element x in the list, and there are C(k-1, xs\{x}) combinations that contain x (i.e. res1), and C(k,xs\{xs}) combinations that do not contain x (i.e. res2 in code).

Full example:

$array = array('1', '2', '3', '4', '5', '6', '7');

function combinationsOf($k, $xs){
        if ($k === 0)
            return array(array());
        if (count($xs) === 0)
            return array();
        $x = $xs[0];
        $xs1 = array_slice($xs,1,count($xs)-1);
        $res1 = combinationsOf($k-1,$xs1);
        for ($i = 0; $i < count($res1); $i++) {
            array_splice($res1[$i], 0, 0, $x);
        }
        $res2 = combinationsOf($k,$xs1);
        return array_merge($res1, $res2);
    }

print_r ($array);
print_r(combinationsOf(5,$array));
//print_r(combinationsOf(5,$array)+combinationsOf(6,$array)+combinationsOf(7,$array));

Answer 3

    function arrToBit(Array $element) {
        $bit = '';
        foreach ($element as $e) {
            $bit .= '1';
        }
        $length = count($element);
        $num = bindec($bit);
        $back = [];
        while ($num) {
            $back[] = str_pad(decbin($num), $length, '0', STR_PAD_LEFT);
            $num--;
        }
        //$back[] = str_pad(decbin(0), $length, '0', STR_PAD_LEFT);
        return $back;
    }

    function bitToArr(Array $element, $bit) {
        $num = count($element);
        $back = [];
        for ($i = 0; $i < $num; $i++) {
            if (substr($bit, $i, 1) == '1') {
                $back[] = $element[$i];
            }
        }
        return $back;
    }

    $tags = ['a', 'b', 'c'];
    $bits = arrToBit($tags);
    $combination = [];
    foreach ($bits as $b) {
        $combination[] = bitToArr($tags, $b);
    }
    var_dump($combination);