本文详解如何手动实现数组全排列算法（即所有可能的顺序组合），基于“下一个字典序排列”思想，通过自定义交换、翻转和迭代逻辑完成，无需调用 permutations()、array_map() 等高级函数，适合学习算法原理与底层实现。
本文详解如何手动实现数组全排列算法（即所有可能的顺序组合），基于“下一个字典序排列”思想，通过自定义交换、翻转和迭代逻辑完成，无需调用 `permutations()`、`array_map()` 等高级函数，适合学习算法原理与底层实现。
在 PHP 中生成一个数组（如 [1,2,3,4]）的所有全排列（permutations）——注意：此处是「排列」而非「组合」（combinations），因为问题中要求的是 4! = 24 种不同顺序（如 1234, 1243, 1324…），而非子集组合（如 {1,2}, {1,3,4}）。用户原代码使用四层嵌套循环遍历下标 0–3，结果得到 $4^4 = 256$ 种重复允许、顺序不限的笛卡尔积，这实际是「有放回的排列」；而真正的全排列要求每个元素恰好出现一次，且顺序唯一。
要纯手工实现（不依赖 pcntl_fork、iterator_to_array 或 eval 等非常规手段），核心是模拟经典的 Next Lexicographical Permutation Algorithm（字典序下一排列算法），其步骤如下：
- 初始排序：确保输入数组升序（最小字典序排列），作为起点；
-
寻找可交换对：从右向左扫描，找到第一个满足
nums[j] 的最右位置对 <code>(j, i)（即j是最大可能的“可提升位”）； -
交换：将
nums[j]与右侧大于它的最小元素nums[i]交换； -
翻转后缀：将
j+1到末尾的子数组反转，使后缀变为升序（获得紧邻的下一个最小排列）； - 循环直到无法再生成新排列（即整个数组降序，已达最大字典序）。
以下是完全手写的、零内置排列函数的实现（仅含 sort() —— 可轻松替换为冒泡/插入排序，文末提供替代方案）：
<?php
// 自定义交换函数
function swap(&$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
// 自定义区间翻转函数（闭区间 [left, right]）
function reverse(&$arr, $left, $right) {
while ($left < $right) {
swap($arr, $left++, $right--);
}
}
// 手动冒泡排序（替代内置 sort()，满足“无函数”要求）
function bubbleSort(&$arr) {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
swap($arr, $j, $j + 1);
}
}
}
}
// 主函数：生成全部排列（返回二维数组）
function getAllPermutations($numbers) {
$arr = $numbers; // 工作副本
bubbleSort($arr); // 升序初始化（关键！）
$result = [$arr]; // 存储首个排列
while (true) {
$n = count($arr);
$i = $j = -1;
// 步骤2：找最大 j，使得存在 i > j 且 arr[j] < arr[i]
for ($k = $n - 1; $k >= 0; $k--) {
for ($l = $k - 1; $l >= 0; $l--) {
if ($arr[$l] < $arr[$k] && ($j === -1 || $j < $l)) {
$i = $k;
$j = $l;
}
}
}
// 若未找到，说明已是最后一个排列（降序）
if ($j === -1) break;
// 步骤3：交换
swap($arr, $i, $j);
// 步骤4：翻转 j+1 到末尾
reverse($arr, $j + 1, $n - 1);
// 记录新排列（注意：需 array_values 重置键，保证数值索引）
$result[] = array_values($arr);
}
return $result;
}
// 使用示例
$numbers = [1, 2, 3, 4];
$perms = getAllPermutations($numbers);
echo "共生成 " . count($perms) . " 个全排列：<br><br>";
foreach ($perms as $index => $perm) {
echo ($index + 1) . ". [" . implode(", ", $perm) . "]<br>";
}
?>✅ 输出结果（前5项示意）：
立即学习“PHP免费学习笔记（深入）”；
- [1, 2, 3, 4]
- [1, 2, 4, 3]
- [1, 3, 2, 4]
- [1, 3, 4, 2]
- [1, 4, 2, 3]
… - [4, 3, 2, 1]
? 关键注意事项：
- 该算法时间复杂度为 $O(n! \times n)$，适用于中小规模数组（≤8 个元素），大数据量请改用迭代器或外部库；
- 每次
array_values($arr)确保返回标准数字索引数组，便于后续in_array()或循环比对随机数； - 若需去重（处理含重复元素的数组如
[1,1,2]），需在swap前增加判重逻辑（比较相邻值跳过重复交换）； - 所有函数（
swap、reverse、bubbleSort）均为手写，彻底规避next_permutation、range、array_reduce等任何“组合相关”内置函数。
掌握此算法不仅能解决当前问题，更是理解 STL std::next_permutation、Python itertools.permutations 底层逻辑的基础——排列的本质，是状态机在字典序空间中的确定性游走。
