多数组全排列
写在前面
写代码的时候遇到一个看似简单的问题，才让我深刻理解到算法对于编程的重要性，未来重心要放到算法的研究，算法研究是程序员开拓思维提高境界必经之路。
问题分析
问题出现场景
- 给你几个数组分别是：
$arr1 = ['高端银','玫瑰金','深空灰'];
$arr2 = ['32G','64G','128G'];
$arr3 = ['国行','港版','美版'];
- 问：如何获得三个数组的全排列？，即
result[0] = '高端银，32G, 国行';
result[1] = '高端银，32G, 港版';
result[2] = '高端银，32G, 美版';
result[3] = '高端银，64G, 国行';
.....
result[26] = '深空灰，128G, 美版';
- 这个其实不难，分别遍历三次，每次三个元素也就是 3x3x3 生成 27个排列组合。
$delimiter = ',';
$result = array();
foreach($arr1 as $a1){
foreach($arr2 as $a2){
foreach($arr3 as $a3){
$item = $a1.$delimiter.$a2.$delimiter.$a3;
array_push($result, $item);
}
}
}
var_dump($result);
算法分析
那么问题来了？如果给的数据源数组个数不一定，以及每个数组元素个数不确定，以及每个元素的元素个数，如果才能获得不定数组的全排列呢？
- 错误解题思路：
最初我一看到这个问题，就一股脑的分析到底需要循环多少次，然后越想越糊涂，因为这本来就是一个不定循环，具体循环多少次完全取决于你的数据源（我定义为：$target）
- 正确解题思路：
- 以具体案例分析场景，最初我使用 2个数组，以及 3 个数组源，找规律
- 学会拆封过程，因为拆封过程你就发现规律。
- 分析结果：
1.这种类型的设计思路其实就是，首选数据源的前两个数组进行卡迪尔积运算，生成新的数组，然后新的数组跟数据源的下一个数组进行卡迪尔积运算，最终生成一个拥有元素个数为 每个数组元素个数乘积的新数组，即：sizeof($result) = sizeof($arr1)xsizeof($arr2)x....sizeof($arrn); 2. 这种类型使用递归来解决，只需要注意递归的跳出问题
- 溢出问题
- 如果数据源只有一个元素，不能进行卡迪尔积运算，跳出；
- 如果运算次数超过了数据源本身个数，跳出；
代码实现
最终代码
/** 多数组排列
* @param $target 数据源
* @param int $depth 运行深度,默认 0
* @param array $result 中间结果
* @param string $delimiter 结果分隔符
* @return array|null 结果
*/
function arrOrder($target, $depth = 0, $result = array(), $delimiter = ',')
{
// 判断数据源个数是否大于0
if (sizeof($target) < 2) {
return (isset($target[0]))? $target[0] : null;
}
// 判断当前运算深度是否导致数据源溢出
if ($depth >= sizeof($target) - 1) {
return $result;
}
$result = ($result) ? $result : $target[$depth];
$rs = array();
foreach ($result as $r) {
foreach ($target[$depth + 1] as $a) {
$item = $r . $delimiter . $a;
array_push($rs, $item);
}
}
$depth++;
// 进行递归
return arrOrder($target, $depth, $rs, $delimiter);
}
运行结果
$target = [
['高端银', '玫瑰金', '深空灰'],
['32G', '64G', '128G'],
['国行', '港版', '美版'],
];
$result = arrOrder($target);
var_dump($result);
-------- 结果 ---------
array (size=27)
0 => string '高端银,32G,国行' (length=20)
1 => string '高端银,32G,港版' (length=20)
2 => string '高端银,32G,美版' (length=20)
3 => string '高端银,64G,国行' (length=20)
4 => string '高端银,64G,港版' (length=20)
5 => string '高端银,64G,美版' (length=20)
6 => string '高端银,128G,国行' (length=21)
7 => string '高端银,128G,港版' (length=21)
8 => string '高端银,128G,美版' (length=21)
9 => string '玫瑰金,32G,国行' (length=20)
10 => string '玫瑰金,32G,港版' (length=20)
11 => string '玫瑰金,32G,美版' (length=20)
12 => string '玫瑰金,64G,国行' (length=20)
13 => string '玫瑰金,64G,港版' (length=20)
14 => string '玫瑰金,64G,美版' (length=20)
15 => string '玫瑰金,128G,国行' (length=21)
16 => string '玫瑰金,128G,港版' (length=21)
17 => string '玫瑰金,128G,美版' (length=21)
18 => string '深空灰,32G,国行' (length=20)
19 => string '深空灰,32G,港版' (length=20)
20 => string '深空灰,32G,美版' (length=20)
21 => string '深空灰,64G,国行' (length=20)
22 => string '深空灰,64G,港版' (length=20)
23 => string '深空灰,64G,美版' (length=20)
24 => string '深空灰,128G,国行' (length=21)
25 => string '深空灰,128G,港版' (length=21)
26 => string '深空灰,128G,美版' (length=21)