经过一周的搜索,将许多其他语言的算法转换为php,生成一个包含"n中的组合k"的数组。我被卡住了。请帮帮我。
这是我的代码(使用php):
function comb($item,$arr,$out, $start, $n, $k, $maxk) {
if ($k > $maxk) {
foreach($arr as $ar){
echo "$ar";
echo "<br/>";
}
return;
}
for ($i=$start; $i<=$n; $i++) {
$arr[$k] = $item[$i-1];
comb($isi, $arr, $out, $i+1, $n, $k+1, $maxk);
}
}
$team = array("A","B","C","D");
$ar = array();
$o = array();
comb($team,$ar,$o,1,4,1,2);
上面的递归算法真的让我很困惑。上面的代码成功地形成了组合,但由于它的递归特性,我无法将它们合并到一个数组中。我只想制作一个数组,其中包含4项中2项的组合结果。像这样(见下文)
Array (
[0] => Array (
[1] => A
[2] => B
)
[1] => Array (
[1] => A
[2] => C
)
[2] => Array (
[1] => A
[2] => D
)
[3] => Array (
[1] => B
[2] => C
)
[4] => Array (
[1] => B
[2] => D
)
[5] => Array (
[1] => C
[2] => D
)
)
我知道我离答案还很远。但请引导我,找到答案。也许你知道另一种技巧,这并不重要。如果你的代码有效,我会使用它。无论你使用了什么技术。如有任何想法,我们将不胜感激,谢谢。。!
一个(我认为)更简单的递归实现是:
<?php
/* Given the array $A, returns the array of $k-subsets
of $A in lexicographical order. */
function k_lex_subset($A,$k) {
if (($k <= 0) or (count($A) < $k)) { return array(); }
else if ($k <= 1) { return array_chunk($A,1); }
else {
$v = array_shift($A);
$AwA = k_lex_subset($A,$k-1);
foreach($AwA as &$vp) {
array_unshift($vp,$v);
}
$AwoA = k_lex_subset($A,$k);
$resultArrs = array_merge($AwA, $AwoA);
return($resultArrs);
}
}
$team = array("A","B","C","D");
print_r(k_lex_subset($team,2));
?>
返回
Array
(
[0] => Array
(
[0] => A
[1] => B
)
[1] => Array
(
[0] => A
[1] => C
)
[2] => Array
(
[0] => A
[1] => D
)
[3] => Array
(
[0] => B
[1] => C
)
[4] => Array
(
[0] => B
[1] => D
)
[5] => Array
(
[0] => C
[1] => D
)
)
并且将适用于任何大小的阵列和任何$k
。
您要查找的术语是(字典)k-子集枚举,在这种特定情况下,$k
是2。
解释
这个想法很简单。假设我们有(例如)一个集合{A,B,C,D}
。我们想从所有包含A的集合开始,因此我们考虑来自{B,C,D}
的大小为1以下的子集,并将A附加到它们上,从而产生
{{A,B}, {A,C}, {A,D}}
然后我们考虑中没有A的大小为2的所有子集
{{B,C}, {B,D}, {C,D}}
然后我们把两者合并。希望很容易看出,一般来说,这是如何产生一个很好的递归策略来构建集合的k子集(而不仅仅是k=2)的。
参考
关于这类事情的一个极好的参考是克努思的《计算编程的艺术》第4卷第3节。
这应该可以达到上面描述的数组:
<?php
$array = array("A","B","C","D");
function transformArray( $array ) {
$returnArray = array();
for( $i=0; $i < count($array); $i++ ) {
for( $j=$i+1; $j < count($array); $j++ ) {
$returnArray[] = array( $array[$i], $array[$j] );
}
}
return $returnArray;
}
print_r(transformArray($array));
?>
不完全确定start、n和k的必要性,但这应该会得到预期的输出。如果您提供更多关于为什么需要这些计数器的详细信息,我们可以为您提供更全面的答案。
function comb($itemArray, $start, $n, $k, $maxk) {
//if ($k > $maxk) return;
$outputArray = array();
foreach($itemArray AS $index => $firstChar) {
for($i = $index+1; $i<count($itemArray); $i++) {
$secondChar = $itemArray[$i];
$outputArray[] = array($firstChar, $secondChar);
}
}
return $outputArray;
}
$teamArray = array("A","B","C","D");
$resultArray = comb($teamArray,1,4,1,2);
ppr($resultArray);
function ppr($variable) {
echo '<pre>';
print_r($variable);
echo '</pre>';
}
function comb($a, $len){
if ($len > count($a))return array();
$out = array();
if ($len==1) {
foreach ($a as $v) $out[] = array($v);
return $out;
}
$len--;
while (count($a) > $len) {
$b = array_shift($a);
$c = comb($a, $len);
foreach ($c as $v){
array_unshift($v, $b);
$out[] = $v;
}
}
return $out;
}
$test = array('a','b','c','d');
$a = comb($test,2);
print_r($a);
会给你:
Array(
[0] => Array
(
[0] => a
[1] => b
)
[1] => Array
(
[0] => a
[1] => c
)
[2] => Array
(
[0] => a
[1] => d
)
[3] => Array
(
[0] => b
[1] => c
)
[4] => Array
(
[0] => b
[1] => d
)
[5] => Array
(
[0] => c
[1] => d
)
)
为什么要进行
echo "ar"
而不是
echo $ar
你还在寻找排列或组合吗?这里有一个非常好的算法的网站。实现是用java实现的,但它非常清晰。因此转换为php并不困难:http://geekviewpoint.com/Numbers_functions_in_java/
如果您想要一种纯粹干净的递归方式,请使用以下方法:
function comb($item, $n) {
return comb_rec($item, array(), $n);
}
function comb_rec($items, $c, $n) {
if (count($c) == $n) {
return array($c);
}else{
if (count($items) == 0) {
return $items;
}else{
$list = $items;
$head = array_shift($list);
$tail = $list;
$current = $c;
array_push($current,$head);
return array_merge(comb_rec($tail, $current, $n),comb_rec($tail, $c, $n));
}
}
}
$team = array("A","B","C","D");
$all = comb($team,2);
print_r($all);