比如:
{2,11,32,35,64,72,87,90,99,102}我要找到所有小于1000的组合。eg:2 x 11 = 22 < 1000 ------------------>{2,11}
2 x 32 = 64 < 1000 ------------------>{2,32}
用循环如果只有几个数还能写,如果上百个数怎么办????
{2,11,32,35,64,72,87,90,99,102}我要找到所有小于1000的组合。eg:2 x 11 = 22 < 1000 ------------------>{2,11}
2 x 32 = 64 < 1000 ------------------>{2,32}
用循环如果只有几个数还能写,如果上百个数怎么办????
<?php
$array = array(2,11,32,35,64,44,29,72,87,90,99,102,100,55,200,77);
$len = count($array);
sort($array);for($i=0;$i<$len;$i++)
{
$tmpNum = 1000/$array[$i];
for($j=$i+1;$j<$len;$j++)
{
if($j<=$tmpNum)
{
$finalArr[] = $array[$i].",".$array[$j];
}
}
}
echo "<pre>";
print_r($finalArr);
echo "</pre>";
?>
$array = array(2,11,32,35,64,44,29,72,87,90,99,102,100,55,200,77);
$len = count($array);
sort($array);for($i=0;$i<$len;$i++)
{
$tmpNum = 1000/$array[$i];
for($j=$i+1;$j<$len;$j++)
{
if($array[$j]<=$tmpNum)
{
$finalArr[] = $array[$i].",".$array[$j];
}
}
}
echo "<pre>";
print_r($finalArr);
echo "</pre>";
?>
sort($arr);while($val=current($arr))
{
if( $val >= 100 ) //可调为1000
{
array_splice($arr,array_search($val,$arr));
}
next($arr);
}print_r($arr);/*
//output
//Array ( [0] => 2 [1] => 11 [2] => 29 [3] => 32 [4] => 35 [5] => 44 [6] => 55 [7] => 64 [8] => 72 [9] => 77 [10] => 87 [11] => 90 [12] => 99 )
*/数组基数大的,可以从递归判断数组中间值开始。
[/CDOE]
$arr = array(2,11,32,35,64,44,29,72,87,90,99,102,100,55,200,77);
sort($arr);while($val=current($arr)){
if( $val >= 100 )
array_splice($arr,array_search($val,$arr));
next($arr);
}
{$arr[1]}
{$arr[1], $arr[2]}
{$arr[1], $arr[2], $arr[3]}
{$arr[1], $arr[2], $arr[3], $arr[4]}
这些相乘只要没达到给出的值,这里是1000,都符合条件,就是要把这些组合都找出来
$arr = array(2,11,32,35,64,44,29,72,87,90,99,102,100,55,200,77);
sort($arr);while($val=current($arr))
{
if( $val*next($arr) >= 1000 )
{
array_splice($arr,array_search($val,$arr));
}
next($arr);
}print_r($arr);
//output
//Array ( [0] => 2 [1] => 11 [2] => 29 [3] => 32 )
于是改成循环了,觉得反而逻辑上更清楚一点,
你可以再修改优化一下,
不过在数组成员多的情况下,这个结果集本身也会急剧变大, (我想网上可以找到这个相关的计算公式,会有用)
<?php$arr = array (2, 11, 32, 35, 64, 72, 87, 90, 99, 102 );
//$arr = range ( 2, 245, 5 );$target = 1000;$results [0] = array ();for($i = 1; $i <= count ( $arr ); $i ++) {
// 利用上一次的结果生成下一次的
$results [$i] = findFactors ( $arr, $i, $results [$i - 1] );
}print_r ( $results );function findFactors($arr, $level, $factors = array()) { global $target; if ($level < 1) {
return $factors;
} if ($level == 1) {
return array_map ( 'toArray', array_filter ( $arr, 'lessThanTarget' ) );
} if ($level > count ( $arr )) {
return array ();
} $new = array ();
foreach ( $arr as $v ) {
foreach ( $factors as $factor ) {
if (count ( $factor ) != $level - 1) { // 可删
continue;
}
if ($v <= max ( $factor )) { // 避免重复结果
continue;
}
if (array_product ( $factor ) * $v < $target) {
$new [] = array_merge ( $factor, array ($v ) );
}
}
}
return $new;}function lessThanTarget($value) {
global $target;
return $value <= $target;
}function toArray($x) {
return array ($x );
}
<?php
$array = array(2,11,32,35,64,44,29,72,87,90,99,102,100,55,200,77);
sort($array);foreach($array as $f_k=>$f_v)
{
foreach($array as $s_k=>$s_v)
{
if($f_k==$s_k){
continue;
}
if($f_v*$s_v<=1000)
{
$finalArr[] = $f_v.",".$s_v;
}
}
}
echo "<pre>";
print_r($finalArr);
echo "</pre>";
?>
$v *= $w;
return $v;
}for($i=2; $i<count($ar); $i++) {
foreach(combination($ar, $i) as $row) {
if(array_reduce($row, 'rmul', 1) < 1000) {
$out[] = $row;
}
}
}
print_r($out);
Array
(
[0] => Array
(
[0] => 2
[1] => 11
) [1] => Array
(
[0] => 2
[1] => 32
) [2] => Array
(
[0] => 11
[1] => 32
) [3] => Array
(
[0] => 2
[1] => 35
) [4] => Array
(
[0] => 11
[1] => 35
) [5] => Array
(
[0] => 2
[1] => 64
) [6] => Array
(
[0] => 11
[1] => 64
) [7] => Array
(
[0] => 2
[1] => 72
) [8] => Array
(
[0] => 11
[1] => 72
) [9] => Array
(
[0] => 2
[1] => 87
) [10] => Array
(
[0] => 11
[1] => 87
) [11] => Array
(
[0] => 2
[1] => 90
) [12] => Array
(
[0] => 11
[1] => 90
) [13] => Array
(
[0] => 2
[1] => 99
) [14] => Array
(
[0] => 2
[1] => 102
) [15] => Array
(
[0] => 2
[1] => 11
[2] => 32
) [16] => Array
(
[0] => 2
[1] => 11
[2] => 35
))其中 combination :
/**
* 函数 combination
* 功能 m取n的组合函数
**/
if(! function_exists('combination')):
function combination($ar, $k, $m=0, $a=array()) {
static $ret = array();
if($m == 0) {
$m = count($ar);
$ret = array();
}
for($i=$m; $i>=$k; $i--) {
$a[$k-1] = $ar[$i-1];
if($k > 1) {
combination(&$ar, $k-1, $i-1, $a);
}else {
array_unshift ($ret, array_reverse($a));
}
}
return $ret;
}
endif;
$m = array(4,16,64,5);
$len = count($m);function getGroup($i, $len, $product, $vproduct, $arr, $level, $k){
if(($level+1) == $k){ //最后一层
for($p=$i+1;$p<$len;$p++){
$vproduct1 = $vproduct * $arr[$p];
echo $vproduct1 . ":" . $product . '*$m[' . $p . ']<br />';
}
} else if(($level+1) < $k){ //还未到最后一层,还需要进一步操作
for($j=$i+1;$j<$len-1;$j++){
$level1 = $level+1;
$vproduct1 = $vproduct * $arr[$j];
$product1 = $product . '*$m[' . $j . ']';
getGroup($j, $len, $product1, $vproduct1, $arr, $level1, $k);
}
} else if($k == 1){ //只有一个元素
for($p=$i;$p<$len;$p++){
echo $arr[$p] . ":" . '$m[' . $p . ']<br />';
}
}
}for($k=1;$k<=$len;$k++){
echo "<hr />" , $k , "个元素的组合:<br />";
if($k == 1){
getGroup(0, $len, "", 0, $m, 1, $k);
} else{
for($i=0;$i<$len-$k+1;$i++){
$level1 = 1;
$product = '$m[' . $i . ']';echo "<br />";
$vproduct = $m[$i];
getGroup($i, $len, $product, $vproduct, $m, $level1, $k);
}
}
}