PHP实现排列组合算法

php排列组合的算法

<?php

$keyword_list = ['mysql', '数据库', '权限'];

//求2个元素作为一个整体的排列数组
$list = arrangement($keyword_list, 2);
echo '<pre>';
print_r($list);

//求2个元素作为一个整体的排列数组个数
$num = arrangementNum(count($keyword_list), 2);
echo $num . "\n";

//求2个元素作为一个整体的组合数组
$list = combination($keyword_list, 2);
echo '<pre>';
print_r($list);

//求2个元素作为一个整体的组合数组个数
$num = combinationNum(count($keyword_list), 2);
echo $num . "\n";

// 阶乘
function factorial($n) {
    return array_product(range(1, $n));
}

// 排列数
function arrangementNum($n, $m) {
    return factorial($n) / factorial($n - $m);
}

// 组合数
function combinationNum($n, $m) {
    return arrangementNum($n, $m) / factorial($m);
}

// 排列
function arrangement($array, $m) {
    $r = array();

    $n = count($array);
    if ($m <= 0 || $m > $n) {
        return $r;
    }

    for ($i = 0; $i < $n; $i++) {
        $b = $array;
        $t = array_splice($b, $i, 1);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $c = arrangement($b, $m - 1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }

    return $r;
}

// 组合
function combination($array, $m) {
    $r = array();

    $n = count($array);
    if ($m <= 0 || $m > $n) {
        return $r;
    }

    for ($i = 0; $i < $n; $i++) {
        $t = array($array[$i]);
        if ($m == 1) {
            $r[] = $t;
        } else {
            $b = array_slice($array, $i + 1);
            $c = combination($b, $m - 1);
            foreach ($c as $v) {
                $r[] = array_merge($t, $v);
            }
        }
    }

    return $r;
}

关于排列更高效的算法方法

function arrangementV2($array, $num) {
    $result = [];

    if ($num == 1) {
        foreach ($array as $key => $value) {
            $result[] = [$key => $value];
        }

        return $result;
    }

    ksort($array);
    $subArray = array_slice($array, 1, null, true);
    $subArrayResult = arrangementV2($subArray, $num - 1);

    foreach ($array as $key => $value) {
        foreach ($subArrayResult as $v1) {
            $ext = array_keys($v1);
            if ($key < array_shift($ext)) {
                $result[] = [$key => $value] + $v1;
            }
        }
    }

    return $result;
}

声明：本文由用户投稿上传，本站不保证内容的真实与正确性，并且不承担相关法律责任，如有侵权请提供版权资料并联系删除！

编程笔记 » PHP实现排列组合算法