PHP Algorithm to Generate All Combinations of a Specific Size from a Single Set

PHP algorithm to generate all combinations of a specific size from a single set

I would use a recursive function. Here's a (working) example with comments. Hope this works for you!

function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);

}

// example
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);
/*
array(9) {
  [0]=>
  string(2) "aa"
  [1]=>
  string(2) "ab"
  [2]=>
  string(2) "ac"
  [3]=>
  string(2) "ba"
  [4]=>
  string(2) "bb"
  [5]=>
  string(2) "bc"
  [6]=>
  string(2) "ca"
  [7]=>
  string(2) "cb"
  [8]=>
  string(2) "cc"
}
*/

Efficient PHP algorithm to generate all combinations / permutations of inputs

Give this a shot:

<?php
$chars = array('a','b','c');
$count = 13;

$generator = genCombinations($chars,$count);
foreach ($generator as $value) {
  // Do something with the value here
  echo $value;
}

function genCombinations($values,$count=0) {
  // Figure out how many combinations are possible:
  $permCount=pow(count($values),$count);

  // Iterate and yield:
  for($i = 0; $i < $permCount; $i++)
    yield getCombination($values, $count, $i);
}

// State-based way of generating combinations:
function getCombination($values, $count, $index) {
  $result=array();
  for($i = 0; $i < $count; $i++) {
    // Figure out where in the array to start from, given the external state and the internal loop state
    $pos = $index % count($values);

    // Append and continue
    $result[] = $values[$pos];
    $index = ($index-$pos)/count($values);;
  }
  return $result;
}

It is a state-based fixed-length combination generator that should hopefully fit the bill. It will only accept arrays and will return combinations of the array items, regardless of what is actually stored in the array.

Every (specific sized) combination from set/array with no duplicate items

Alright - all possible subsets without duplicates and assuming that the order does not matter, i.e. [1, 2, 3, 4, 5] is the same as [5, 4, 3, 2, 1]. Minimalistic example:

<?php
$arr = array(1, 2, 3, 4, 5, 6, 7);

function getSubsets($set, $items) {
  $result = array();
  getSubsets2($set, $items, 0, array(), $result);
  return $result;
}

function getSubsets2($set, $items, $index, $current, &$result) {
  if (sizeof($current) === $items) {
    $result[] = $current;
    return;
  }
  if ($index < sizeof($set)) {
    getSubsets2($set, $items, $index + 1, $current, $result);
    $current[] = $set[$index];
    getSubsets2($set, $items, $index + 1, $current, $result);
  }
}

$subsets = getSubsets($arr, 5);

echo(sizeof($subsets)); // 21
?>

Not to carry off someone else's laurels: This is 100% based on another Stack Overflow answer written in java.

Get all ordered, contiguous combinations of an array's elements

• We can use array_slice() function to take a chunk out of the input array. It will also ensure that the order is maintained, as well as the combinations are of the successive values (as per the original array).
• Now, we need to use two nested loops, to determine $offset, and $length for the chunk.
• $offset value will basically loop from the beginning to end; $length will initially be count of remaining values from the offset, and it will be decrementing upto 2 (we don't want single values as combinations).

Try the following (Rextester DEMO):

$str = 'word1 word2 word3 word4';
$words = explode(' ', $str);

$combinations = array();

// offset from start to end of the words
for($offset = 0; $offset < count($words); $offset++) {

    // length from available remaining words to 2
    for ($length = count($words) - $offset; $length > 1; $length--) {

        // get the array chunk
        $combinations[] = array_slice($words, $offset, $length);
    }
}

// test output
print_r($combinations);

Output:

Array
(
    [0] => Array
        (
            [0] => word1
            [1] => word2
            [2] => word3
            [3] => word4
        )

    [1] => Array
        (
            [0] => word1
            [1] => word2
            [2] => word3
        )

    [2] => Array
        (
            [0] => word1
            [1] => word2
        )

    [3] => Array
        (
            [0] => word2
            [1] => word3
            [2] => word4
        )

    [4] => Array
        (
            [0] => word2
            [1] => word3
        )

    [5] => Array
        (
            [0] => word3
            [1] => word4
        )

)

Non-repeating combination of specific count in PHP

It's basically the same structure, just check if the day is already in the combination before adding it.

function sampling($days, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of days
    if (empty($combinations)) {
        $combinations = array_map(function($day) { return array($day); }, $days);
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($days as $day) {
            if (!in_array($day, $combination)) {
                $new_combination = $combination;
                $new_combination[] = $day;
                $new_combinations[] = $new_combination;
            }
        }
    }

    # call same function again for the next iteration
    return sampling($days, $size - 1, $new_combinations);
}

DEMO

How to generate in PHP all combinations of items in multiple arrays

Here is recursive solution:

function combinations($arrays, $i = 0) {
    if (!isset($arrays[$i])) {
        return array();
    }
    if ($i == count($arrays) - 1) {
        return $arrays[$i];
    }

    // get combinations from subsequent arrays
    $tmp = combinations($arrays, $i + 1);

    $result = array();

    // concat each array from tmp with each element from $arrays[$i]
    foreach ($arrays[$i] as $v) {
        foreach ($tmp as $t) {
            $result[] = is_array($t) ? 
                array_merge(array($v), $t) :
                array($v, $t);
        }
    }

    return $result;
}

print_r(
    combinations(
        array(
            array('A1','A2','A3'), 
            array('B1','B2','B3'), 
            array('C1','C2')
        )
    )
);

---

Related Topics