一个数组，怎么找到乘积小于某一个数的组合，并保留

Question

比如：
{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} 
用循环如果只有几个数还能写，如果上百个数怎么办？？？？

Answer 1

这只是两个数乘积值小于1000，多个数的很复杂！不知楼主是否有这个需求？
<?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>";
?>

Answer 2

不好意思，刚才的代码有误，这个是好的<?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($array[$j]<=$tmpNum)
{
$finalArr[] =  $array[$i].",".$array[$j];
}
}
}
echo "<pre>";
print_r($finalArr);
echo "</pre>";
?>

Answer 3

[CODE=PHP]$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 ) //可调为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]

Answer 4

$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);
}

Answer 5

帖子不能直接修改了我再说清楚一点这个组合可能是一个元素，也可能两个，也可能全部元素全乘起来也没1000，这个是根据给出的数组决定的。eg:
{$arr[1]}
{$arr[1], $arr[2]}
{$arr[1], $arr[2], $arr[3]}
{$arr[1], $arr[2], $arr[3], $arr[4]}
这些相乘只要没达到给出的值，这里是1000，都符合条件，就是要把这些组合都找出来

Answer 6

$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 )

Answer 7

先写成递归,但是报了递归层数太多的错,
于是改成循环了,觉得反而逻辑上更清楚一点,
你可以再修改优化一下, 
不过在数组成员多的情况下,这个结果集本身也会急剧变大, (我想网上可以找到这个相关的计算公式,会有用)
<?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 );
}

Answer 8

用了一下二楼的代码
<?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>";
?>

Answer 9

这只是一个组合问题，只是对组合的结果进行一下过滤而已$ar = array(2,11,32,35,64,72,87,90,99,102);function rmul($v, $w) {
  $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;

Answer 10

虽然结贴了，还是忍不住自己写了一个代码，大家可以试试
$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);
}
}
}