php 全排序实现

全排列的概念

全排列是指将一组元素的所有可能的排列组合列举出来。例如，数组 [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 = count($items) - 1; $i >= 0; --$i) {
            $newItems = $items;
            $newPerms = $perms;
            list($tmp) = array_splice($newItems, $i, 1);
            array_unshift($newPerms, $tmp);
            permute($newItems, $newPerms, $result);
        }
    }
    return $result;
}

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

使用 Heap 算法

Heap 算法是一种高效的全排列生成算法，通过交换元素位置减少递归深度。

function heapPermutation(&$array, $size, &$result) {
    if ($size == 1) {
        $result[] = $array;
        return;
    }
    for ($i = 0; $i < $size; $i++) {
        heapPermutation($array, $size - 1, $result);
        if ($size % 2 == 1) {
            $temp = $array[0];
            $array[0] = $array[$size - 1];
            $array[$size - 1] = $temp;
        } else {
            $temp = $array[$i];
            $array[$i] = $array[$size - 1];
            $array[$size - 1] = $temp;
        }
    }
}

// 示例调用
$array = [1, 2, 3];
$result = [];
heapPermutation($array, count($array), $result);
print_r($result);

使用内置函数生成排列

PHP 的 permutations 方法可以通过第三方库（如 math-php）或自定义函数实现。

// 使用 math-php 库（需安装）
use Math\Combinatorics\Permutation;
$permutation = new Permutation();
$result = $permutation->getPermutations([1, 2, 3]);
print_r($result);

性能优化建议

• 对于大规模数据，递归可能导致栈溢出，建议使用迭代方法优化。
• 使用生成器（Generator）减少内存占用，避免存储所有排列结果。

function permuteGenerator($items, $perms = []) {
    if (empty($items)) {
        yield $perms;
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
            $newItems = $items;
            $newPerms = $perms;
            list($tmp) = array_splice($newItems, $i, 1);
            array_unshift($newPerms, $tmp);
            foreach (permuteGenerator($newItems, $newPerms) as $perm) {
                yield $perm;
            }
        }
    }
}

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

以上方法可以根据需求选择，递归和 Heap 算法适合小规模数据，生成器适合处理大规模排列。