PHP-php求一个高效的组合算法

WordPress 开发 WordPress 开发 主题:1098 回复:2322

PHP-php求一个高效的组合算法

泛泛之交 发布于 2017-10-07 字数 254 浏览 1150 回复 4

给出a,b,c,d,e,f,g等元素,想自由生成相关的组合,组合从一位开始
a
b
..
a,b
a,c
a,d
...
a,b,c
a,b,c,d
......
生成所有组合对顺序没有要求,即a,b 和 b,a可以当同一条,不用重复出现,请列出所有的组合。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(4

虐人心 2017-10-16 4 楼

一个的组合就是集合里元素的数量
两个的 就是1个与后面的元素组合 第二个与他后面的元素组合 通解就是第二个与他后面的元素的组合
三个的 借助两个的 和较小的那个元素后面的进行组合 当然刨除借助的两个 例如ac可以和b组合成acb 但是 bc却不能和a组合 因为b这两个里最小的 所以不可以组合
至于第四个 我想不需要在解释了

写这么多想法 也没能给你一句代码 实在抱歉 说出想法 是拓展思路 而帮你实现则对我对你均无益处

瑾兮 2017-10-15 3 楼

原理就是用七位二进制数代表七个元素,用这个数分别和(64,32,16,8,4,2,1)做位运算得出为1的位数输出,然后把这个数减一递归,代码贴上:

<?php
$total_number=64+32+16+8+4+2+1;

print_combination($total_number);

//位运算函数
function bit_operation($input)
{
// echo $input." ";
$values = array(64,32,16,8,4,2,1);
$stack = array();
foreach($values as $value)
{
$bit=$value&$input;
array_push($stack,$bit);
}
// print_r($stack);
return $stack;
}

//输出函数
function print_combination($input)
{
if($input>0){
$results=bit_operation($input);
echo "t";
foreach($results as $result)
{
// echo $result;
if($result==64){echo a;}
elseif($result==32){echo b;}
elseif($result==16){echo c;}
elseif($result==8){echo d;}
elseif($result==4){echo e;}
elseif($result==2){echo f;}
elseif($result==1){echo g;}
}
print_combination(--$input,$values);
}
}

?>

浮生未歇 2017-10-15 2 楼

借助于pear的Math_Combinatorics扩展很方便的,
Math_Combinatorics

<?php
require 'Math/Combinatorics.php';
$arr = array('a','b','c','d','e','f','g');

$combinatorics = new Math_Combinatorics;
foreach( range(1, count($arr)) as $subset_size ) {
foreach($combinatorics->permutations($arr, $subset_size) as $p) {
echo join(' ', $p), "n";
}
}

想挽留 2017-10-11 1 楼

二进制方式做一个非递归的。

function combination($arr)
{
$len = count($arr);
foreach($arr as $k => $v)
{
    $total += pow(2,$k);
}

$ret = array(); for($i=1;$i<=$total;$i++) { $str = substr(str_repeat("0",$len).decbin($i),-$len); $tmparr = array_diff_key($arr,array_diff(str_split($str),array('1'))); $ret[] = implode($tmparr,'');

} return $ret;

}

$arr = array('a','b','c','d','e','f','g'); print_r(combination($arr));