PHP 算法从单个集合生成特定大小的所有组合
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19067556/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
PHP algorithm to generate all combinations of a specific size from a single set
提问by asim-ishaq
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.
我试图推导出一种算法，该算法生成特定大小的所有可能组合，例如接受字符数组和大小作为其参数并返回组合数组的函数。
Example: Let say we have a set of chars: Set A = {A,B,C}
示例：假设我们有一组字符：Set A = {A,B,C}
a) All possible combinations of size 2: (3^2 = 9)
a) 大小 2 的所有可能组合：(3^2 = 9)
AA, AB, AC
BA, BB, BC
CA, CB, CC
b) All possible combinations of size 3: (3^3 = 27)
b) 大小 3 的所有可能组合：(3^3 = 27)
AAA, AAB, AAC,
ABA, ABB, ACC,
CAA, BAA, BAC,
.... ad so on total combinations = 27
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.
请注意，配对大小可能大于种群的总大小。前任。如果 set 包含 3 个字符，那么我们也可以创建大小为 4 的组合。
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.
编辑：另请注意，这与排列不同。在排列中，我们不能有重复的字符，例如如果我们使用排列算法，AA 就不会出现。在统计学中，它被称为抽样。
回答by Joel Hinz
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"
}
*/
回答by cyon
You can do this recursively. Note that as per your definition, the "combinations" of length n+1can be generated from the combinations of length nby taking each combination of length nand appending one of the letters from your set. If you care you can prove this by mathematical induction.
您可以递归地执行此操作。请注意，根据您的定义，长度的“组合” n+1可以n通过获取每个长度组合n并附加您的集合中的一个字母来从长度组合中生成。如果你关心你可以通过数学归纳法证明这一点。
So for example with a set of {A,B,C}the combinations of length 1 are:
因此，例如一{A,B,C}组长度为 1 的组合是：
A, B, C
The combinations of length 2 are therefore
因此长度 2 的组合是
(A, B, C) + A = AA, BA, CA
(A, B, C) + B = AB, BB, BC
(A, B, C) + C = AC, CB, CC
This would be the code and here on ideone
这将是代码，在ideone 上
function comb ($n, $elems) {
if ($n > 0) {
$tmp_set = array();
$res = comb($n-1, $elems);
foreach ($res as $ce) {
foreach ($elems as $e) {
array_push($tmp_set, $ce . $e);
}
}
return $tmp_set;
}
else {
return array('');
}
}
$elems = array('A','B','C');
$v = comb(4, $elems);
回答by Santiago Alessandri
A possible algorithm would be:
一种可能的算法是：
$array_elems_to_combine = array('A', 'B', 'C');
$size = 4;
$current_set = array('');
for ($i = 0; $i < $size; $i++) {
$tmp_set = array();
foreach ($current_set as $curr_elem) {
foreach ($array_elems_to_combine as $new_elem) {
$tmp_set[] = $curr_elem . $new_elem;
}
}
$current_set = $tmp_set;
}
return $current_set;
Basically, what you will do is take each element of the current set and append all the elements of the element array.
基本上，您要做的是获取当前集合的每个元素并附加元素数组的所有元素。
In the first step: you will have as result ('a', 'b', 'c'), after the seconds step: ('aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc')and so on.
在第一步：你将得到结果('a', 'b', 'c')，在第二步之后：('aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc')等等。
回答by user1913526
Another idea using numeric base conversion
使用数字基数转换的另一个想法
$items = ['a', 'b', 'c', 'd'];
$length = 3;
$numberOfSequences = pow(count($items), $length);
for ($i = 0; $i < $numberOfSequences; $i++) {
$results[] = array_map(function ($key) use ($items) {
return $items[base_convert($key, count($items), 10)];
}, str_split(str_pad(base_convert($i, 10, count($items), $length, 0, STR_PAD_LEFT)));
}
return $results;
