PHP 算法从单个集合生成特定大小的所有组合 [英] PHP algorithm to generate all combinations of a specific size from a single set

问题描述

我试图推导出一种算法，该算法生成特定大小的所有可能组合，类似于接受字符数组和大小作为其参数并返回组合数组的函数.

I am trying to deduce an algorithm which generates all possible combinations of a specific size something like a function which accepts an array of chars and size as its parameter and return an array of combinations.

示例:假设我们有一组字符:设置 A = {A,B,C}

Example: Let say we have a set of chars: Set A = {A,B,C}

a) 大小 2 的所有可能组合:(3^2 = 9)

a) All possible combinations of size 2: (3^2 = 9)

AA, AB, AC
BA, BB, BC
CA, CB, CC

b) 大小 3 的所有可能组合:(3^3 = 27)

b) All possible combinations of size 3: (3^3 = 27)

AAA, AAB, AAC,
ABA, ABB, ACC,
CAA, BAA, BAC,
.... ad so on total combinations = 27

请注意，配对大小可以大于种群的总大小.前任.如果 set 包含 3 个字符，那么我们也可以创建大小为 4 的组合.

Please note that the pair size can be greater than total size of pouplation. Ex. if set contains 3 characters then we can also create combination of size 4.

编辑:另请注意，这与排列不同.在排列中，我们不能有重复的字符，例如如果我们使用排列算法，AA 就不会出现.在统计学中，它被称为抽样.

EDIT: Also note that this is different from permutation. In permutation we cannot have repeating characters for example AA cannot come if we use permutation algorithm. In statistics it is known as sampling.

推荐答案

我会使用递归函数.这是一个带注释的(工作)示例.希望这对你有用！

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"
}
*/

这篇关于PHP 算法从单个集合生成特定大小的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！