全排列php实现

全排列的PHP实现

全排列是指将一组元素的所有可能的排列组合都列举出来。在PHP中，可以通过递归或迭代的方式实现全排列。以下是两种常见的实现方法：

递归实现

递归是一种直观的实现方式，通过不断缩小问题规模来生成排列。

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;
}

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

迭代实现

迭代方式通过循环和交换元素来生成排列，通常使用堆算法（Heap's algorithm）。

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

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

使用内置函数

PHP的permutations函数可以通过第三方库（如math-php）实现，但标准库中不直接提供全排列函数。可以通过组合array_shift和递归实现类似功能。

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

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

性能优化

对于大型数组，全排列的计算会非常耗时（时间复杂度为O(n!)）。可以通过以下方式优化：

• 使用生成器（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 $permutation) {
                yield $permutation;
            }
        }
    }
}

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

通过以上方法，可以灵活地在PHP中实现全排列功能。