PHP 数组元素->组合算法排列题,求算法解决?

[eluotao]

根据数组元素写出所有组合排列. 条件：组合排列的位数 为数组成员数 例如： 数组 $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 只能算一个值.

有大佬能帮忙看看吗?

这道题有点想不通?

有什么优雅的算法吗?

[rabbbit]

数组值可以为 0 吗?
数组值是有序的吗?
数组值是依次递增的吗?

[rabbbit]

计算出 $arr 元素值 所有 5 位数组合?
这个组合长度可以小于 /大于数组元素个数吗? 例如 4 位数组合 /6 位数组合

[zarte]

值弄个数组
然后循环元素一个个计算值，用 in_array 判断是否有这个值。

[eluotao]

@rabbbit 只计算相加值,所以不需要考虑是不是 0.
数组值 是指定给的 比如 12345 23589 13654 不过都是 10 以内的数.

指定位数 比如 4 5 6 三种.

[rabbbit]

[rabbbit]

不一定对啊,没做测试

[rabbbit]

nums = nums.sort() 这句拿掉,貌似不排序也没影响

[eluotao]

这个是 JS 不是 PHP.
我运行了 显示结果 undefined

[eluotao]

@rabbbit

[takeoffyoung]

N 位数组合的值的集合 = (N-1 位数组合的集合)' * (原集合)
再去重

[eluotao]

@takeoffyoung 我只想到把所有组合都列出来 然后通过计算值 去重.

[dsp2138]

密码字典也是用同类型的算法生成的吗？

[rabbbit]

不会 php,注释一下自己翻译吧
不一定对,如果是生产环境不要求性能别这么写

[shenhhd]

上个月公司遇到类似的问题
计算所有的组合
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]);

[imn1]

需求没说清
1.你的例子有些只有 4 位数
2.全部 5 位排列么？
3.只需要求和，还是要把和与排列都写出来？
前者不用算，[minSum...maxSum]肯定的，后者不穷举么？

[eluotao]

@imn1 少打了一位 算 5 位.

[eluotao]

@shenhhd 多谢 就是你这个.

[eluotao]

@shenhhd 写的真漂亮

[shenhhd]

刚开始的方案是通过进制运算 来获取全部组合的数组下标 但是最后我们这边的数组元素有可能超过 最大的 36 进制

[A3m0n]

@rabbbit VS Code 吗？能否告诉一下颜色主题？

[airdge]

@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());

[eluotao]

@airdge 多谢 新思路

[ProfaneAria]

递归处理，思路如下（例子就用 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]


可能说的不够清楚。原理其实很简单，最后统计加值的时候其实和数字具体在哪个位置无关，所以可以按位数依次加上所有可能的值进行扩展，知道扩展到你想要的位数位置。

[eluotao]

@shenhhd 这个算法 遇上 10 位以上 就不行了. 内存不够搞了.