本文介绍一种不依赖 permute()、array_ 系列或递归函数的纯手工实现方式，通过“下一个字典序排列”算法，手动模拟全排列生成过程，适用于固定长度数组，输出所有不重复的顺序组合。
本文介绍一种不依赖 `permute()`、`array_` 系列或递归函数的纯手工实现方式，通过“下一个字典序排列”算法，手动模拟全排列生成过程，适用于固定长度数组，输出所有不重复的顺序组合。
在 PHP 中生成一个数组（如 [1,2,3,4]）的所有全排列（permutations），而非简单笛卡尔积（即你原代码中 4⁴=256 种重复允许、位置可重用的组合），关键在于理解：全排列要求每个结果都是原数组元素的一个无重复、不遗漏的重排序，共 n! 种（对 4 个元素是 4! = 24 种）。你最初嵌套 4 层 for 循环得到的是「有放回的排列」（即允许重复选取同一索引），因此产生 256 种结果——这实际是 4 位 4 进制数的所有取值，而非真正的全排列。
要严格实现「无重复、不遗漏」的全排列且*不调用任何内置排列函数（如 pcntl_fork, spl_permutation, 或 `array_辅助函数）**，推荐采用经典的 **Next Lexicographic Permutation 算法**（字典序下一个排列）。该算法仅使用基础控制结构（for、while）、比较和交换操作，完全符合“不使用函数”的核心诉求（注：sort()可替换为手写冒泡/选择排序；本文为简洁起见保留sort()` 调用，但明确标注其可自主实现）。
✅ 算法核心步骤（三步走）
- 初始升序排列：将输入数组排序（最小字典序），作为第一个排列；
-
找“可提升位”：从右向左扫描，找到第一个满足
nums[j] 的最靠左索引 <code>j（即存在右侧更大数可与之交换）； -
交换 + 反转后缀：在
j右侧找到大于nums[j]的最小数（即最右满足条件者），与其交换；然后将j+1到末尾的子数组反转（恢复升序，确保下一个是紧邻的字典序）； - 循环直至无法再生成：当整个数组呈非递增（降序）时，已是最后一个排列，终止。
? 完整可运行代码（零外部函数依赖）
<?php
// 手写 swap：交换数组中两个索引的值
function swap(&$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
// 手写 reverse：反转数组指定区间 [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) {
$x = $y = -1; // 初始化查找标记
// 第二步：找最右可交换对（j < i 且 arr[j] < arr[i]，且 j 尽可能靠左）
for ($i = count($arr) - 1; $i >= 0; $i--) {
for ($j = $i - 1; $j >= 0; $j--) {
if ($arr[$j] < $arr[$i]) {
if ($y === -1 || $j > $y) { // 取最靠右的合法 j（即最大 j）
$x = $i;
$y = $j;
}
}
}
}
// 若未找到，说明已达最大字典序（降序），终止
if ($x === -1) break;
// 第三步：交换并反转后缀
swap($arr, $x, $y);
reverse($arr, $y + 1, count($arr) - 1);
$result[] = $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>";
}
?>⚠️ 注意事项与最佳实践
- 时间复杂度：O(n! × n)，因需生成 n! 个排列，每次生成耗时 O(n)；
- 空间安全：所有操作均在副本上进行，原始数组不受影响；
- 去重保障：算法天然避免重复（基于索引交换，非值匹配），若输入含重复数字需额外去重逻辑；
- 扩展性：本实现支持任意数值/字符串数组（只要可比较大小），长度不限（但注意 n > 10 时 n! 增长极快）；
-
对比你的原始方案：你用四重循环本质是
for i in 0..3: for j in 0..3: ...——这是笛卡尔积（允许索引复用），而全排列要求i, j, k, l互不相同，必须引入状态标记或回溯，而 Next Permutation 法巧妙规避了显式标记。
✅ 总结：不依赖
permutations()等高级函数，仅用for、if、swap和reverse即可精准生成全部 24 种排列。其本质是模拟字典序递增过程，稳定、高效、易于理解，且结果天然有序，便于后续与随机数比对（如in_array($randomNums, $perms)）。
