给定如下数组
$array = ('1', '2', '3', '4', '5', '6', '7');
我正在寻找一种生成所有可能组合的方法,每个组合 r 中需要最少数量的元素(例如,如果 r = 5,那么它将返回包含至少 5 个元素的所有可能组合)
可以使用
以下函数递归定义n
项中的k
组合:
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);
}
以上是基于递归定义,即要选择k
n
元素,可以修复列表中的元素x
,并且有C(k-1, xs'{x})
包含x
的组合(即 res1
),以及不包含x
的C(k,xs'{xs})
组合(即 res2
在代码中)。
完整示例:
$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));
组合可以表示为
n C r = n!/(r! -(n-r)!)
首先,我们将$n
确定为数组中元素的数量。$r
是每个组合中元素的最小数量。
$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);
接下来,我们将$max
确定为可以用$n
二进制数字表示的最大数字。也就是说,如果$n = 3
,则$max = (111)
2 = 7
.为此,我们首先创建一个空字符串$maxBinary
并向其添加$n
个1
。然后我们将其转换为十进制,并将其存储在 $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
然后,我们列出从0
到$max
的每个二进制数,并存储那些$r
1
数以上的二进制数。
$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;
}
}
然后,我们使用与上面相同的技巧来为我们的组合选择元素。我相信这些评论足以解释。
$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
}
}
}
仅此而已。大功告成!
现在,如果您有类似的东西
echo count($combs);
然后它会给你29
.
附加说明:
我只是在看到你的问题后才读到这个,作为一个新手,我发现这些很有用:
- 维基百科 - http://en.wikipedia.org/wiki/Combination
- Php 递归以获得字符串的所有可能性
- 从 n 返回 k 个元素的所有组合的算法
此外,这里有一些指向文档的快速链接,应该可以帮助将来看到此内容的人:
- 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
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);
$arr = array(1,2,3,4,5,6);
$check_value =[];
$all_values = [];
CONT:
$result = $check_value;
shuffle($arr);
$check_value = array_slice($arr,0,3);
if(count($check_value) == 3 && serialize($check_value) !== serialize($result)){
$result = $check_value;
array_push($all_values,$result);
goto CONT;
}
print_r($all_values);