当前位置：首页 > PHP

php 全排序实现

2026-01-30 07:56:28PHP

全排列的概念

全排列是指对给定的一组元素，按照一定的顺序进行排列，所有可能的排列方式。例如，对于数组 [1, 2, 3]，其全排列包括 [1, 2, 3]、[1, 3, 2]、[2, 1, 3] 等共 6 种排列。

递归实现全排列

递归是实现全排列的常见方法，通过不断交换元素的位置生成所有可能的排列。

function permute($items, $perms = [], &$result = []) {
    if (empty($items)) {
        $result[] = $perms;
    } else {
        for ($i = 0; $i < count($items); $i++) {
            $newItems = $items;
            $newPerms = $perms;
            list($temp) = array_splice($newItems, $i, 1);
            $newPerms[] = $temp;
            permute($newItems, $newPerms, $result);
        }
    }
    return $result;
}

// 示例用法
$arr = [1, 2, 3];
$result = permute($arr);
print_r($result);

回溯法实现全排列

回溯法通过尝试所有可能的路径，并在发现不满足条件时回退，适用于全排列问题。

function backtrack(&$nums, $start, &$result) {
    if ($start == count($nums)) {
        $result[] = $nums;
        return;
    }
    for ($i = $start; $i < count($nums); $i++) {
        // 交换元素
        list($nums[$start], $nums[$i]) = [$nums[$i], $nums[$start]];
        backtrack($nums, $start + 1, $result);
        // 恢复交换
        list($nums[$start], $nums[$i]) = [$nums[$i], $nums[$start]];
    }
}

// 示例用法
$nums = [1, 2, 3];
$result = [];
backtrack($nums, 0, $result);
print_r($result);

使用库函数实现全排列

PHP 的 permutations 函数可以通过第三方库（如 math-php/combinatorics）实现全排列。

require 'vendor/autoload.php';
use Math\Combinatorics\Combinatorics;

$combinatorics = new Combinatorics;
$permutations = $combinatorics->permutations([1, 2, 3]);
print_r($permutations);

性能优化建议

对于大规模数据，递归和回溯可能消耗较多内存。可以考虑迭代法或使用生成器（Generator）按需生成排列，减少内存占用。

function permutations($items) {
    if (count($items) <= 1) {
        yield $items;
    } else {
        foreach ($items as $i => $item) {
            $remaining = array_merge(array_slice($items, 0, $i), array_slice($items, $i + 1));
            foreach (permutations($remaining) as $permutation) {
                yield array_merge([$item], $permutation);
            }
        }
    }
}

// 示例用法
foreach (permutations([1, 2, 3]) as $perm) {
    print_r($perm);
}