排列组合的仿进制算法

排列组合是一种常见的数学问题,在程序上也经常应用,如多组属性间的交叉组合等。我根据仿进制算法(数值自然升序,当前位到顶归0,下一位加1)来提供一种新的解题思路,程序语言(PHP)。

一维数组的排列组合

var_dump(group(array('a','b','c','d')));

function group($arr = array()){
    $count = count($arr);
    $group = [];
    $num = 1;
    $pin = array();
    for($i = 0; $i < $count; $i++){
        $num *= $count;
        $pin[] = 0;
    }

    $i = 0;
    while($i < $num){
        $s = '';
        $p = array();
        for($j = 0; $j < $count; $j++){
            $p[] = $arr[$pin[$j]];
            $s .= $arr[$pin[$j]];
        }
        if(count(array_unique($p)) == $count){
            $group[] = $s;
        }
        //进制处理
        for($k = 0; $k < $count; $k++){
            if($pin[$k] < $count - 1){
                $pin[$k] += 1;
                break;
            }else{
                $pin[$k] = 0;
                continue;
            }
        }
        $i++;
    }

    return array_unique($group));
}

二维数组的排列组合(常用于属性组合)

$arr = array(
    0 => array('红', '黄', '蓝'),
    1 => array('L', 'M', 'S')
);

var_dump(attr_group($arr));

function attr_group($arr = array()) {

    $group = array(); //最终数组

    if (!empty($arr)) {
        $fresh_arr = array();
        foreach ($arr as $key => $val) {
            $fresh_arr[] = $val;
        }
        $arr = $fresh_arr;

        $t = 0; //计数器
        $num = 1; //元素组合可能性
        $pin = array(); //指针
        $con = array(); //子组成员数量
        foreach ($arr as $key => $val) {
            $pin[$key] = 0;
            $con[$key] = count($val) - 1;
            $num *= count($val);
        }
        $init = count($arr) - 1; //初始长度
        while ($t < $num) { //加入一组数据 $new = array(); foreach ($arr as $key => $val) {
                $new[] = $val[$pin[$key]];
            }
            $group[] = $new;
            //下一组
            $i = $init;
            $pin[$i] += 1;
            while ($pin[$i] > $con[$i]) {
                $pin[$i] = 0;
                if ($i >= 0) {
                    $i--;
                    $pin[$i] += 1;
                }
            }
            $t++;
        }
    }

    return $group;
}


(17) 给我点赞
留言(155)
匿名:哎呦不错哦!
匿名:哎呦不错哦!