首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
华为云
V2EX  ›  PHP

PHP 数组元素->组合算法排列题,求算法解决?

  •  
  •   eluotao · 11 天前 · 1068 次点击

    根据数组元素写出所有组合排列. 条件:组合排列的位数 为数组成员数 例如: 数组 $arr=array('1','2','3','4','5'); 计算出 $arr 元素值 所有 5 位数组合. 例如

    1111

    2222

    3333

    4444

    5555

    12222

    13333

    14444

    15555

    21111

    23333

    24444

    25555

    31111

    32222

    34444

    35555

    41111

    42222

    43333

    45555

    51111

    52222

    53333

    54444

    ....

    ....

    ....

    以此类推.

    通过以上组合 把每个元素值相加

    计算出 11111 = 5

    22222 = 10

    33333 = 15

    44444 = 20

    ....

    ....

    ....

    找出能组合的所有不同值..

    例如 12345 54321 23451 34512 45123 51234 43215 等等 计算和 都是 16 只能算一个值.

    有大佬能帮忙看看吗?

    这道题有点想不通?

    有什么优雅的算法吗?

    24 回复  |  直到 2018-08-12 01:10:49 +08:00
        1
    rabbbit   11 天前
    数组值可以为 0 吗?
    数组值是有序的吗?
    数组值是依次递增的吗?
        2
    rabbbit   11 天前
    计算出 $arr 元素值 所有 5 位数组合?
    这个组合长度可以小于 /大于数组元素个数吗? 例如 4 位数组合 /6 位数组合
        3
    zarte   11 天前
    值弄个数组
    然后循环元素一个个计算值,用 in_array 判断是否有这个值。
        4
    eluotao   11 天前
    @rabbbit 只计算相加值,所以不需要考虑是不是 0.
    数组值 是指定给的 比如 12345 23589 13654 不过都是 10 以内的数.

    指定位数 比如 4 5 6 三种.
        5
    rabbbit   11 天前
        6
    rabbbit   11 天前
    不一定对啊,没做测试
        7
    rabbbit   11 天前
    nums = nums.sort() 这句拿掉,貌似不排序也没影响
        8
    eluotao   11 天前
    这个是 JS 不是 PHP.
    我运行了 显示结果 undefined
        9
    eluotao   11 天前
        10
    takeoffyoung   11 天前
    N 位数组合的值的集合 = (N-1 位数组合的集合)' * (原集合)
    再去重
        11
    eluotao   11 天前
    @takeoffyoung 我只想到把所有组合都列出来 然后通过计算值 去重.
        12
    dsp2138   11 天前
    密码字典也是用同类型的算法生成的吗?
        13
    rabbbit   11 天前

    不会 php,注释一下自己翻译吧
    不一定对,如果是生产环境不要求性能别这么写
        14
    shenhhd   11 天前
    上个月公司遇到类似的问题
    计算所有的组合
    1.递归版本 (同事写的)
    function add_one(&$arr,$list,$num,$str="",$deep=0){
    if($deep==$num){
    $arr[]=$str;
    return;
    }
    foreach($list as $one){
    $str_tmp=$one.$str;
    add_one($arr,$list,$num,$str_tmp,$deep+1);
    }
    }

    $arr=[];
    add_one($arr,[1,2,3,4,5],5);
    var_dump($arr);
    2.普通过程版

    public function test_fun($number, $arr) {
    $arr_len = count($arr) - 1; //下标最大值
    for ($i = 0; $i < $number; $i++) {
    //初始化一个数组
    $arr_key[$i] = 0;
    }
    while (true) {
    $str = '';
    foreach ($arr_key as $v) {
    $str .= $arr[$v];
    }
    echo $str;
    echo PHP_EOL;
    $is_break = true;
    foreach ($arr_key as $k => $v) {
    if ($v == $arr_len) {
    $arr_key[$k] = 0;
    } else {
    $arr_key[$k] = $v + 1;
    $is_break = false;
    break;
    }
    }
    if ($is_break) {
    break;
    }
    }
    }

    test_fun(5, [1,2,3,4,5]);
        15
    imn1   11 天前
    需求没说清
    1.你的例子有些只有 4 位数
    2.全部 5 位排列么?
    3.只需要求和,还是要把和与排列都写出来?
    前者不用算,[minSum...maxSum]肯定的,后者不穷举么?
        16
    eluotao   11 天前
    @imn1 少打了一位 算 5 位.
        17
    eluotao   11 天前
    @shenhhd 多谢 就是你这个.
        18
    eluotao   11 天前
    @shenhhd 写的真漂亮
        19
    shenhhd   11 天前
    刚开始的方案是通过进制运算 来获取全部组合的数组下标 但是最后我们这边的数组元素有可能超过 最大的 36 进制
        20
    A3m0n   11 天前
    @rabbbit VS Code 吗?能否告诉一下颜色主题?
        21
    airdge   11 天前
    @shenhhd @eluotao
    可以用 range 输出 11111 到 55555 的数组,再判新断数组元素有没含有其他的数字,过滤得到新数组
    class Num
    {
    public $array;
    public $count;
    public $unique;
    public $diff;
    public $exec;
    public function __construct($array)
    {
    sort($array);
    $this->array = $array;
    $this->count = count($array);
    $this->unique = array_unique($array);
    $this->diff = array_diff(range(0, 9), $this->unique); //得到差集
    $this->exec = implode('|', $this->diff); // 匹配字符 6|7|8
    }
    public function soft()
    {
    $low = str_pad($this->array[0], $this->count, $this->array[0]);
    $high = str_pad(end($this->array), $this->count, end($this->array));
    $range = range($low, $high);
    $str = array_map(function ($a) {
    if (preg_match('/' . $this->exec . '/', $a)) {
    # 如果匹配到差集的数字,则不输出
    } else {
    return $a;
    }
    }, $range);
    return array_values(array_filter($str));
    }
    }
    $array = [1, 2, 4, 5, 6];
    $a = new Num($array);
    print_r($a->soft());
        22
    eluotao   11 天前
    @airdge 多谢 新思路
        23
    ProfaneAria   11 天前
    递归处理,思路如下(例子就用 1-5,3 位)
    第一次( 1 位数时的可能值)
    $list = [1, 2, 3, 4, 5]
    第二次( 2 位数时的可能值,在 1 位数的基础上处理)
    分别取$list 中的值加上 1~5,1~5 具体位置并不影响最后加值
    1 -> 2, 3, 4, 5, 6
    2 -> 3, 4, 5, 6, 7
    3 -> 4, 5, 6, 7, 8
    ....
    做个并集
    最后$list = [2, 3, 4, 5, 6, 7, 8, 9, 10]
    第三次依次
    最后$list = [3, 4, 5 , 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]


    可能说的不够清楚。原理其实很简单,最后统计加值的时候其实和数字具体在哪个位置无关,所以可以按位数依次加上所有可能的值进行扩展,知道扩展到你想要的位数位置。
        24
    eluotao   9 天前
    @shenhhd 这个算法 遇上 10 位以上 就不行了. 内存不够搞了.
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2103 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 19ms · UTC 13:48 · PVG 21:48 · LAX 06:48 · JFK 09:48
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1