从m个数中选择n个数的实现

84 阅读 0 评论 56 点赞

我是靠谱客的博主可耐手链，最近开发中收集的这篇文章主要介绍从m个数中选择n个数的实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

[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]

解法一、

<?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 "]";
    }
}

解法二、

<?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;
        }
    }
}

解法三、

<?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));