四脚猫每日一题-从m个数中选择n个数

Posted by & filed under 每日一题.

【四脚猫】每日一题（4月9日） ：从m个数中选出n个数来 ( 0 < n <= m) ，要求n个数之间不能有重复，其和等于一个定值k。求一段程序，罗列所有的可能。 例如备选的数字是：11, 18, 12, 1, -2, 20, 8, 10, 7, 6 。 和k等于：18 那么组合的可能有：

1
2
3
4
5
6
7
8
9
10
[18]
[8,10]
[-2,20]
[12,6]
[11,7]
[11,1,6]
[1,10,7]
[12,-2,8]
[12,1,-2,7]
[11,1,-2,8]

AN的解法很巧妙，采用二进制按位乘后加和，这个很有创意！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
$nums = array(11,18,12,1,-2,20,8,10,7,6);
for($i=0;$i<1024;$i++){
    $str = str_split(strrev(decbin($i)));
    $ans = 0;
    foreach($str as $k=>$v){
        $ans +=$v *$nums[$k];
    }
    if($ans==18) {
        echo '[';
        foreach($str as $k=>$v){
            if($v==1) {
                echo $nums[$k];echo ",";
            }
        }
        echo "]";
    }
}

风兮蜻蜒和刘文千采用递归的方式找子集，这个代码大家赶紧收藏啊，以后还能用得到啊！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
<?php

/**
 * 组合枚举
 */
function c($arr, $n, &$res, $pre = array())
{
    if ($n == 0)
    {
        $res[] = $pre;
    }
    else
    {
        $count = count($arr);
        for ($i = 0; $i < $count - $n + 1; $i++)
        {
            $temp = array_shift($arr);
            c($arr, $n - 1, $res, array_merge($pre, array(
                $temp
            )));
        }
    }
}
// 处理数组
$arr = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6, 12, 6, 6, 6, -6 );
$sum = 18; // 条件和值

$count = count($arr);
// 从C(18,1) 循环到 C(18,18)
for ($i = 1; $i <= $count; $i++)
{
    $res = array();
    c($arr, $i, $res);
    foreach ($res as $val)
    {
        if (array_sum($val) == $sum)
        {
            echo implode(' + ', $val), ' = ', $sum, PHP_EOL;
        }
    }
}

Diven精益求精，完成后第二天又提交了超过32位的解法，厉害!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?php
function sum_eq_constant($arr, $constant) {
    if (empty($arr) || !is_array($arr) || !is_numeric($constant))return false;
    sort($arr);
    $m      = count($arr);
    $max    = pow(2, $m); //有2的m次方种可能 (包括全部为零)
    $step   = 0;
    $result = array();
    while ($step < $max) {
        $zero_one_arr = array(); //定义一个0,1数组
        $tmp          = array(
            $step
        );
        for ($i = 0; $i < $m; $i++) { //用辗转相除法 把十进制 转成二进制
            $zero_one_arr[$i] = $tmp[$i] % 2;
            $tmp[$i + 1]      = floor($tmp[$i] / 2);
        }
        $multi = array();
        foreach ($zero_one_arr as $k => $v) {
            $multi[] = $v * $arr[$k];
        }
        if (array_sum($multi) == $constant) {
            $result[] = array_diff($multi, array(
                0,
                '0'
            ));
        }
        $step++;
    }
    return $result;
}
$arr      = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6 );
$constant = 18;
print_r(sum_eq_constant($arr, $constant));

云无心 的substr和array_diff_key已经用到出神入化了，解法很优美！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
function getCombine($arr, $n) {
    $len   = count($arr);
    $total = pow(2, $len);
    $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'
        )));
        if (array_sum($tmparr) == $n) {
            $ret[] = implode($tmparr, ',');
        }
    }
    return array_unique($ret);
}
$data = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6 );
$n    = 18;
print_r(getCombine($data, $n));

青菜虫的堆栈思想很独特，目前逻辑还有遗漏，看能否完善下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
<?php
header('Content-Type: text/html; charset=utf-8');

$arr = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6);

echo '
';
print_r($arr);
print_r(test($arr, 18));
echo '';


function test($arr, $k) {
    sort($arr);
    $m = count($arr);
    $sum = 0;
    $result = array();
    $paths = array();

    for ($i=0; $i<$m; $i++) {
        $tmp = $pointer = array();
        $tmp[] = $arr[$i];
        $pointer[] = $i;
        for ($j=$i+1; $j<$m; $j++) {
            $sum = array_sum($tmp) + $arr[$j];
            $path = implode('-', $pointer);
            if (isset($paths[$path])) continue;

            if ($sum >= $k) {
                if ($sum == $k) {
                    $result[] = array_merge($tmp, array($arr[$j]));
                }
                array_pop($tmp);
                $j = array_pop($pointer);
                $paths[$path] = 1;
            } elseif ($sum < $k) {
                array_push($tmp, $arr[$j]);
                array_push($pointer, $j);
            }
        }
    }
    return $result;
}

// END OF FILE

欢迎各位攻城狮，各位大牛给每日一题投稿，大家可以把自己碰到的有趣问题，工作中碰到的难题等…发送到 稿件邮箱：2313427189@qq.com