PHP实现数字排列

数字排列的基本概念

数字排列指将一组数字按照特定顺序重新组合，常见于算法题或实际开发需求中。PHP提供了多种方式实现数字排列，包括递归、迭代以及内置函数组合。

使用递归实现全排列

递归是解决排列问题的经典方法，通过不断缩小问题规模生成所有可能的排列组合。

function permute($nums) {
    $result = [];
    $used = array_fill(0, count($nums), false);
    backtrack($nums, [], $used, $result);
    return $result;
}

function backtrack($nums, $current, &$used, &$result) {
    if (count($current) === count($nums)) {
        $result[] = $current;
        return;
    }
    for ($i = 0; $i < count($nums); $i++) {
        if (!$used[$i]) {
            $used[$i] = true;
            $current[] = $nums[$i];
            backtrack($nums, $current, $used, $result);
            array_pop($current);
            $used[$i] = false;
        }
    }
}

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

使用内置函数生成排列

PHP的array_permutations函数（需自定义或通过库实现）可简化操作，但标准库未直接提供此功能。可通过以下方式模拟：

function array_permutations($items) {
    if (count($items) <= 1) {
        return [$items];
    }
    $perms = [];
    foreach ($items as $i => $item) {
        $remaining = $items;
        array_splice($remaining, $i, 1);
        foreach (array_permutations($remaining) as $permutation) {
            $perms[] = array_merge([$item], $permutation);
        }
    }
    return $perms;
}

迭代法实现排列

通过堆栈模拟递归过程，避免递归深度限制问题：

function iterativePermute($nums) {
    $stack = [[$nums, []]];
    $result = [];
    while (!empty($stack)) {
        list($remaining, $current) = array_pop($stack);
        if (empty($remaining)) {
            $result[] = $current;
        } else {
            foreach ($remaining as $i => $num) {
                $newRemaining = $remaining;
                array_splice($newRemaining, $i, 1);
                $stack[] = [$newRemaining, array_merge($current, [$num])];
            }
        }
    }
    return $result;
}

处理重复数字的排列

若输入包含重复数字（如[1,1,2]），需去重：

function permuteUnique($nums) {
    sort($nums);
    $result = [];
    backtrackUnique($nums, [], array_fill(0, count($nums), false), $result);
    return $result;
}

function backtrackUnique($nums, $current, $used, &$result) {
    if (count($current) === count($nums)) {
        $result[] = $current;
        return;
    }
    for ($i = 0; $i < count($nums); $i++) {
        if ($used[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$used[$i - 1])) {
            continue;
        }
        $used[$i] = true;
        $current[] = $nums[$i];
        backtrackUnique($nums, $current, $used, $result);
        array_pop($current);
        $used[$i] = false;
    }
}

性能优化建议

• 对于大规模数据，递归可能导致栈溢出，优先选择迭代法。
• 使用yield生成器逐步返回结果，减少内存占用：

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