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

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

  •  
  •   eluotao · 2018-08-10 09:19:30 +08:00 · 2994 次点击
    这是一个创建于 2057 天前的主题,其中的信息可能已经有所发展或是发生改变。

    根据数组元素写出所有组合排列. 条件:组合排列的位数 为数组成员数 例如: 数组 $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
    rabbbit
        1
    rabbbit  
       2018-08-10 09:24:14 +08:00
    数组值可以为 0 吗?
    数组值是有序的吗?
    数组值是依次递增的吗?
    rabbbit
        2
    rabbbit  
       2018-08-10 09:27:55 +08:00
    计算出 $arr 元素值 所有 5 位数组合?
    这个组合长度可以小于 /大于数组元素个数吗? 例如 4 位数组合 /6 位数组合
    zarte
        3
    zarte  
       2018-08-10 09:36:08 +08:00
    值弄个数组
    然后循环元素一个个计算值,用 in_array 判断是否有这个值。
    eluotao
        4
    eluotao  
    OP
       2018-08-10 09:38:14 +08:00
    @rabbbit 只计算相加值,所以不需要考虑是不是 0.
    数组值 是指定给的 比如 12345 23589 13654 不过都是 10 以内的数.

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

    不会 php,注释一下自己翻译吧
    不一定对,如果是生产环境不要求性能别这么写
    shenhhd
        14
    shenhhd  
       2018-08-10 10:46:26 +08:00
    上个月公司遇到类似的问题
    计算所有的组合
    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]);
    imn1
        15
    imn1  
       2018-08-10 10:49:28 +08:00
    需求没说清
    1.你的例子有些只有 4 位数
    2.全部 5 位排列么?
    3.只需要求和,还是要把和与排列都写出来?
    前者不用算,[minSum...maxSum]肯定的,后者不穷举么?
    eluotao
        16
    eluotao  
    OP
       2018-08-10 10:52:05 +08:00
    @imn1 少打了一位 算 5 位.
    eluotao
        17
    eluotao  
    OP
       2018-08-10 10:54:46 +08:00
    @shenhhd 多谢 就是你这个.
    eluotao
        18
    eluotao  
    OP
       2018-08-10 11:28:21 +08:00
    @shenhhd 写的真漂亮
    shenhhd
        19
    shenhhd  
       2018-08-10 11:34:40 +08:00
    刚开始的方案是通过进制运算 来获取全部组合的数组下标 但是最后我们这边的数组元素有可能超过 最大的 36 进制
    A3m0n
        20
    A3m0n  
       2018-08-10 11:57:52 +08:00
    @rabbbit VS Code 吗?能否告诉一下颜色主题?
    airdge
        21
    airdge  
       2018-08-10 15:34:05 +08:00
    @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());
    eluotao
        22
    eluotao  
    OP
       2018-08-10 18:16:07 +08:00
    @airdge 多谢 新思路
    ProfaneAria
        23
    ProfaneAria  
       2018-08-10 20:11:05 +08:00
    递归处理,思路如下(例子就用 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]


    可能说的不够清楚。原理其实很简单,最后统计加值的时候其实和数字具体在哪个位置无关,所以可以按位数依次加上所有可能的值进行扩展,知道扩展到你想要的位数位置。
    eluotao
        24
    eluotao  
    OP
       2018-08-12 01:10:49 +08:00
    @shenhhd 这个算法 遇上 10 位以上 就不行了. 内存不够搞了.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3046 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 12:49 · PVG 20:49 · LAX 05:49 · JFK 08:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.