根据数组元素写出所有组合排列. 条件:组合排列的位数 为数组成员数 例如: 数组 $arr=array('1','2','3','4','5'); 计算出 $arr 元素值 所有 5 位数组合. 例如
1111
2222
3333
4444
5555
12222
13333
14444
15555
21111
23333
24444
25555
31111
32222
34444
35555
41111
42222
43333
45555
51111
52222
53333
54444
....
....
....
以此类推.
通过以上组合 把每个元素值相加
计算出 11111 = 5
22222 = 10
33333 = 15
44444 = 20
....
....
....
找出能组合的所有不同值..
例如 12345 54321 23451 34512 45123 51234 43215 等等 计算和 都是 16 只能算一个值.
有大佬能帮忙看看吗?
这道题有点想不通?
有什么优雅的算法吗?
1
rabbbit 2018-08-10 09:24:14 +08:00
数组值可以为 0 吗?
数组值是有序的吗? 数组值是依次递增的吗? |
2
rabbbit 2018-08-10 09:27:55 +08:00
计算出 $arr 元素值 所有 5 位数组合?
这个组合长度可以小于 /大于数组元素个数吗? 例如 4 位数组合 /6 位数组合 |
3
zarte 2018-08-10 09:36:08 +08:00
值弄个数组
然后循环元素一个个计算值,用 in_array 判断是否有这个值。 |
4
eluotao OP |
5
rabbbit 2018-08-10 10:12:13 +08:00
|
6
rabbbit 2018-08-10 10:13:14 +08:00
不一定对啊,没做测试
|
7
rabbbit 2018-08-10 10:21:27 +08:00
nums = nums.sort() 这句拿掉,貌似不排序也没影响
|
8
eluotao OP 这个是 JS 不是 PHP.
我运行了 显示结果 undefined |
10
takeoffyoung 2018-08-10 10:34:46 +08:00
N 位数组合的值的集合 = (N-1 位数组合的集合)' * (原集合)
再去重 |
11
eluotao OP @takeoffyoung 我只想到把所有组合都列出来 然后通过计算值 去重.
|
12
dsp2138 2018-08-10 10:41:52 +08:00
密码字典也是用同类型的算法生成的吗?
|
13
rabbbit 2018-08-10 10:45:56 +08:00
|
14
shenhhd 2018-08-10 10:46:26 +08:00
上个月公司遇到类似的问题
计算所有的组合 1.递归版本 (同事写的) function add_one(&$arr,$list,$num,$str="",$deep=0){ if($deep==$num){ $arr[]=$str; return; } foreach($list as $one){ $str_tmp=$one.$str; add_one($arr,$list,$num,$str_tmp,$deep+1); } } $arr=[]; add_one($arr,[1,2,3,4,5],5); var_dump($arr); 2.普通过程版 public function test_fun($number, $arr) { $arr_len = count($arr) - 1; //下标最大值 for ($i = 0; $i < $number; $i++) { //初始化一个数组 $arr_key[$i] = 0; } while (true) { $str = ''; foreach ($arr_key as $v) { $str .= $arr[$v]; } echo $str; echo PHP_EOL; $is_break = true; foreach ($arr_key as $k => $v) { if ($v == $arr_len) { $arr_key[$k] = 0; } else { $arr_key[$k] = $v + 1; $is_break = false; break; } } if ($is_break) { break; } } } test_fun(5, [1,2,3,4,5]); |
15
imn1 2018-08-10 10:49:28 +08:00
需求没说清
1.你的例子有些只有 4 位数 2.全部 5 位排列么? 3.只需要求和,还是要把和与排列都写出来? 前者不用算,[minSum...maxSum]肯定的,后者不穷举么? |
19
shenhhd 2018-08-10 11:34:40 +08:00
刚开始的方案是通过进制运算 来获取全部组合的数组下标 但是最后我们这边的数组元素有可能超过 最大的 36 进制
|
21
airdge 2018-08-10 15:34:05 +08:00
@shenhhd @eluotao
可以用 range 输出 11111 到 55555 的数组,再判新断数组元素有没含有其他的数字,过滤得到新数组 class Num { public $array; public $count; public $unique; public $diff; public $exec; public function __construct($array) { sort($array); $this->array = $array; $this->count = count($array); $this->unique = array_unique($array); $this->diff = array_diff(range(0, 9), $this->unique); //得到差集 $this->exec = implode('|', $this->diff); // 匹配字符 6|7|8 } public function soft() { $low = str_pad($this->array[0], $this->count, $this->array[0]); $high = str_pad(end($this->array), $this->count, end($this->array)); $range = range($low, $high); $str = array_map(function ($a) { if (preg_match('/' . $this->exec . '/', $a)) { # 如果匹配到差集的数字,则不输出 } else { return $a; } }, $range); return array_values(array_filter($str)); } } $array = [1, 2, 4, 5, 6]; $a = new Num($array); print_r($a->soft()); |
23
ProfaneAria 2018-08-10 20:11:05 +08:00
递归处理,思路如下(例子就用 1-5,3 位)
第一次( 1 位数时的可能值) $list = [1, 2, 3, 4, 5] 第二次( 2 位数时的可能值,在 1 位数的基础上处理) 分别取$list 中的值加上 1~5,1~5 具体位置并不影响最后加值 1 -> 2, 3, 4, 5, 6 2 -> 3, 4, 5, 6, 7 3 -> 4, 5, 6, 7, 8 .... 做个并集 最后$list = [2, 3, 4, 5, 6, 7, 8, 9, 10] 第三次依次 最后$list = [3, 4, 5 , 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 可能说的不够清楚。原理其实很简单,最后统计加值的时候其实和数字具体在哪个位置无关,所以可以按位数依次加上所有可能的值进行扩展,知道扩展到你想要的位数位置。 |