javascript 数组排列组合

Question

现在要实现一个，类似于排列组合的方法，给定一个数组(数组内全部是数字)，变化数组内每个值的，形成不同的组合。就像下面这样。

例如：[2,2,3] 排列出 223 = 12个不同组合

[

[1,1,1],[1,1,2],[1,1,3],

[1,2,1],[1,2,2],[1,2,3],

[2,1,1],[2,1,2],[2,1,3],

[2,2,1],[2,2,2],[2,2,3]

]

注:[2,2,3] 是不定的数字与数据长度，听起来有点可怕(这要遍历多少次啊)，可实际需求就是这样

补充: 如果是固定数组长度，@superme已经给出答案，现在的问题是：未知数组长度与数字大小，目前我能想到的方式是，使用 eval 来处理未知数，加上superme的方法遍历，这样比递归稍简单一些。请问大家还有什么好的方法吗？

如果大家有好的办法，或实现方案，由于本人理解能力偏低，大神们请尽量上一个实现函数，在下感激不尽。

Answer 1

&nbsp;var arr = [2, 2, 3];&nbsp; var p = []&nbsp; for (var i = 1; i <= arr[0]; i++) {&nbsp; &nbsp; for (var j = 1; j <= arr[1]; j++) {&nbsp; &nbsp; &nbsp; for (var k = 1; k <= arr[2]; k++) {&nbsp; &nbsp; &nbsp; &nbsp; p.push([i, j, k])&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; }&nbsp; console.log(p);&nbsp; &nbsp; let arr = [2,4,2,3];&nbsp; &nbsp; var _arr = [];&nbsp; &nbsp; for (var i = 0; i < arr.length; i++) {&nbsp; &nbsp; &nbsp; var s = [];&nbsp; &nbsp; &nbsp; for (var j = 1; j <= arr[i]; j++) {&nbsp; &nbsp; &nbsp; &nbsp; s.push(j);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; _arr.push(s);&nbsp; &nbsp; }&nbsp; &nbsp;var p =&nbsp; _arr.reduce(function (pre, cur) {&nbsp; &nbsp; &nbsp; var a = [];&nbsp; &nbsp; &nbsp; for (var i = 0; i < pre.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for (var j = 0; j < cur.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a.push([].concat(pre[i], cur[j]))&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp;return a;&nbsp; &nbsp; })&nbsp; &nbsp; console.log(p)应该可以nlog(n) 时间复杂度,但是不会let arr = [23,35,23,36,5];var _arr = [];for (var i = 0; i < arr.length; i++) {&nbsp; var s = [];&nbsp; for (var j = 1; j <= arr[i]; j++) {&nbsp; &nbsp; s.push(j);&nbsp; }&nbsp; _arr.push(s);}var p = [];function f(arr) {&nbsp; var len = arr.length;&nbsp; if (len < 2) {&nbsp; &nbsp; return arr[0];&nbsp; }&nbsp; var mid = Math.ceil(len / 2),&nbsp; &nbsp; left = arr.slice(0, mid),&nbsp; &nbsp; right = arr.slice(mid);&nbsp; return z(f(left), f(right));}function z(left, right) {&nbsp; var a = [];&nbsp; for (var i = 0; i < left.length; i++) {&nbsp; &nbsp; for (var j = 0; j < right.length; j++) {&nbsp; &nbsp; &nbsp; a.push([].concat(left[i], right[j]))&nbsp; &nbsp; }&nbsp; }&nbsp; return p.concat(a);}console.log(p)最后一种效率会高一点

Answer 2

&nbsp; &nbsp;var arr = [2, 2, 3,2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var curr=[];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(var i=1;i<=arr.length;i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; curr.push(1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var result=[];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push(curr.concat());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var len=arr.length;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fk:while(true){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var a=curr[len-1]++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(var i=len-1;i>=0;i--){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(curr[i]>arr[i]){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(i>=1){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; curr[i-1]++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; curr[i]=1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break fk;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var t=curr.concat();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push(t);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; console.log(result);和一楼的做法不一样， 这个思路是，每次最后一位 +1 ，然后检查，是不是需要定位了， 定位的条件是 初始给的数组每个位的值。

Answer 3

如果你最多是3个数据，就是supreme的方法就好了，如果还可能更多的数据，甚至数据数不定，这个其实要用递归或者分治算法（用来解决递归算法层数过多的问题），这个就比较复杂了。其实这个问题用位运算是比较好算的，也可以结合分治来处理：根据数组元素数量N，可以分成N段二进制数据位根据每个数据元素An,则N段二进制数位的值范围就可以得出（二进制位数），并有一个对应的最大值An-1所有的组合就和这个N段2进制位数（假设总共有M位），则0-2^M-1共2^M个数中滤除各段不符合情况后的数据，根据段分开后对应值的组合，即遍历0-这个二进制数范围内这样遍历一遍0-2^M，滤除各段不符合的情况就可以得出所有合适情况了。以[2,2,3]为例来介绍，我们从低位开始作为处理2,表示1,2 二种状态，对应1位二进制，最大值2-1=12,表示1,2 二种状态，对应1位二进制，最大值2-1=13，表示1,2,3 3种状态，对应2位二进制，最大值3-1=2这样，需要1+1+2共4位二进制数来表示所有组合，其中还需要滤除最高位的2个段的一些情况（2位2进制数其实可以表示4种状态的），后面注意是低位开始对应00 0 0，对应1,1,100 0 1, 对应2,1,100 1 0，对应1,2,100 1 1，对应2,2,101 0 0，对应1,1,201 0 1，对应2,1,201 1 0，对应1,2,201 1 1，对应2,2,210 0 0，对应1,1,310 0 1，对应2,1,310 1 0，对应1,2,310 1 1，对应2,2,311 0 0 位段超出不符合11 0 1 位段超出不符合11 1 0 位段超出不符合11 1 1 位段超出不符合算法思路就介绍到这里，实现其实不是太复杂，不过如果位数太多了（超出语言处理范围）还是需要分治这个问题如果真实的规模比较大，还需要考虑空间复杂度和时间复杂度问题，递归肯定是不行的，就是转换递归为循环，空间复杂度也不一定好（当然实际情况下也不该由javascript来处理这么大复杂度的问题，但仍需考虑不是）。这里再给出一个循环的方式var arr = [2,2,3,2,5];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;function MC(inarr,n){&nbsp; &nbsp; var rt=[];&nbsp; &nbsp; for(var i=0;i<inarr.length;i++){&nbsp; &nbsp; &nbsp; &nbsp;for(var j=1;j<=n;j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;var t=inarr[i].concat();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;t.push(j);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;rt.push(t)&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; }&nbsp; &nbsp; return rt;}var mrt=[[]];for(var i=0;i<arr.length;i++){&nbsp; &nbsp; mrt=MC(mrt,arr[i]);}console.log(mrt);