当前位置：首页 > PHP

php 实现排列

2026-01-29 21:46:08PHP

排列的基本概念

排列是指从一组元素中按照一定顺序选取部分或全部元素的不同组合方式。在PHP中，排列可以通过递归或迭代的方式实现。

递归实现排列

递归方法通过不断缩小问题规模来生成排列。每次选择一个元素作为起始，然后对剩余元素进行排列。

php 实现排列

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

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

迭代实现排列

迭代方法通过逐步构建排列，避免递归可能带来的性能问题。使用堆栈来模拟递归过程。

php 实现排列

function permuteIterative($array) {
    $stack = [[$array, []]];
    $result = [];
    while (!empty($stack)) {
        list($items, $perms) = array_pop($stack);
        if (empty($items)) {
            $result[] = $perms;
        } else {
            for ($i = count($items) - 1; $i >= 0; --$i) {
                $newItems = $items;
                $newPerms = $perms;
                list($val) = array_splice($newItems, $i, 1);
                $newPerms[] = $val;
                $stack[] = [$newItems, $newPerms];
            }
        }
    }
    return $result;
}

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

使用内置函数生成排列

PHP标准库中没有直接生成排列的函数，但可以通过组合使用array_shift、array_merge等函数实现。

function generatePermutations($array) {
    if (count($array) <= 1) {
        return [$array];
    }
    $permutations = [];
    foreach ($array as $key => $value) {
        $remaining = $array;
        array_splice($remaining, $key, 1);
        foreach (generatePermutations($remaining) as $permutation) {
            $permutations[] = array_merge([$value], $permutation);
        }
    }
    return $permutations;
}

// 示例用法
$permutations = generatePermutations([1, 2, 3]);
print_r($permutations);

性能优化建议

对于大规模数据，递归方法可能导致栈溢出或性能下降。可以考虑使用迭代方法或借助生成器（Generator）来减少内存消耗。

function permuteGenerator($items, $perms = []) {
    if (empty($items)) {
        yield $perms;
    } else {
        for ($i = 0; $i < count($items); ++$i) {
            $newItems = $items;
            $newPerms = $perms;
            list($val) = array_splice($newItems, $i, 1);
            $newPerms[] = $val;
            yield from permuteGenerator($newItems, $newPerms);
        }
    }
}

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