最近在研究彩票的问题,有一个关于复式数的分解问题始终在困扰我。
例子
- PHP code
/** 比如4个号码分解成3个号码和2个号码 4码:[1,2,3,4] 一组号码 分解成3码后:[1,2,3] [1,2,4] [1,3,4] [2,3,4] 四组三位数的号码 分解成2码后:[1,2] [1,3] [1,4] [2,3] [2,4] [3,4] 六组二位数的号码 不考虑位置 又如5个号码分解成4个号码 4码:[1,2,3,4,5] 一组号码 分解成4码后:[1,2,3,4] [1,2,3,5] [1,2,4,5] [1,3,4,5] [2,3,4,5]四组四位数的号码 分解成3码后:[1,2,3] [1,2,4] [1,2,5] [1,3,4] [1,3,5] [1,4,5] [2,3,4] [2,3,5] [2,4,5] [3,4,5] 十组三位数的号码 分解成2码后:[1,2] [1,3] [1,4] [1,5] [2,3] [2,4] [2,5] [3,4] [3,5] [4,5] 十组二位数的 ------------------------------------------------- 大家应该看出规律了吧 谁能帮我写个方法 array lottery(array $num, int $i){ } @param $num 是指一组数字 @param $i 是指分解的码数 返回结果数组 如 $arr1 = lottery(array(1,2,3,4,5), 4); $arr2 = lottery(array(1,2,3,4,5), 3); 此时 $arr1 的值应该是一个数组 [1,2,3,4] [1,2,3,5] [1,2,4,5] [1,3,4,5] [2,3,4,5] 而$arr2 的值也是一个数组 分解成3码后:[1,2,3] [1,2,4] [1,2,5] [1,3,4] [1,3,5] [1,4,5] [2,3,4] [2,3,5] [2,4,5] [3,4,5] 这个问题我反复研究过,貌似挺难的。。过年了,给66分,祝答题者六六大顺 */
------解决方案--------------------
我复制贴过来吧, 这个实现还是比较高效的算法.
- PHP code
function Combination($arr, $size = 1) { $len = count($arr); $max = pow(2,$len) - pow(2,$len-$size); $min = pow(2,$size)-1; $r_arr = array(); for ($i=$min; $i<=$max; $i++){ $count = 0; $t_arr = array(); for ($j=0; $j<$len; $j++){ $a = pow(2, $j); $t = $i&$a; if($t == $a){ $t_arr[] = $arr[$j]; $count++; } } if($count == $size){ $r_arr[] = $t_arr; } } return $r_arr; } $r = Combination(array(1,2,3,4,5),3); echo '<pre>'; print_r($r); echo '</pre>'; /* Array ( [0] => Array ( [0] => 1 [1] => 2 [2] => 3 ) [1] => Array ( [0] => 1 [1] => 2 [2] => 4 ) [2] => Array ( [0] => 1 [1] => 3 [2] => 4 ) [3] => Array ( [0] => 2 [1] => 3 [2] => 4 ) [4] => Array ( [0] => 1 [1] => 2 [2] => 5 ) [5] => Array ( [0] => 1 [1] => 3 [2] => 5 ) [6] => Array ( [0] => 2 [1] => 3 [2] => 5 ) [7] => Array ( [0] => 1 [1] => 4 [2] => 5 ) [8] => Array ( [0] => 2 [1] => 4 [2] => 5 ) [9] => Array ( [0] => 3 [1] => 4 [2] => 5 ) ) */