排列组合问题
今天同事问了我一个问题,给定随机几个数字(不重复),列出其所有排列组合可能.
这个问题看似很简单,毕竟排列组合大家都学过,都知道总可能数为n!,可是要想列出所有可能,似乎就没那么轻松了.
经过一个午饭时间的思考,终于想除了一个比较low的解决方法
问题分析
略,有空再补上
代码示例
Talk is cheap, show you my code!
<?php
class Permutation
{
public $result = [];
/**
* 生成排列组合
* @param array $in_arr 待排数字
* @param array $out_arr 已排数字
*/
public function generateArray($in_arr, $out_arr = [])
{
$len = count($in_arr);
if ($len == 1) { // 输入集只有一个,则取完数据
$this->result[] = array_merge($out_arr, [$in_arr[0]]); // 生成的排列组合储存
}
for ($i = 0; $i < $len; $i++) {
$tem = array_merge($out_arr, [$in_arr[$i]]); // 将取出数字放入结果集
$this->getArray(unsetI($in_arr, $i), $tem); // 递归取出下一结果集
}
}
}
/**
* 删除索引为i的值且重排索引
* @param $arr
* @param $i
* @return array
*/
function unsetI($arr, $i)
{
unset($arr[$i]);
return array_values($arr);
}
/*---------测试代码--------------*/
$class = new Permutation();
$class->generateArray([1, 2, 3, 4]);
echo "总共:" . count($class->result) , PHP_EOL;
pr($class->result);
function pr($arr)
{
foreach ($arr as $item) {
foreach ($item as $value) {
echo $value;
}
echo PHP_EOL;
}
}
输出
总共:24
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
最后的话
以上代码仅是个人解法,希望诸位能够在评论区列出自己的解法或者思路供笔者参考.
