首頁猿問 javascript 數組排列組合

javascript 數組排列組合

JavaScript

MMTTMM 2019-03-08 18:19:50

現在要實現一個，類似于排列組合的方法，給定一個數組(數組內全部是數字)，變化數組內每個值的，形成不同的組合。就像下面這樣。例如：[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的方法遍歷，這樣比遞歸稍簡單一些。請問大家還有什么好的方法嗎？如果大家有好的辦法，或實現方案，由于本人理解能力偏低，大神們請盡量上一個實現函數，在下感激不盡。

查看完整描述

3 回答

慕后森

TA貢獻1802條經驗獲得超5個贊

var arr = [2, 2, 3];

var p = []

for (var i = 1; i <= arr[0]; i++) {

for (var j = 1; j <= arr[1]; j++) {

for (var k = 1; k <= arr[2]; k++) {

p.push([i, j, k])

}

console.log(p);

let arr = [2,4,2,3];

var _arr = [];

for (var i = 0; i < arr.length; i++) {

var s = [];

for (var j = 1; j <= arr[i]; j++) {

s.push(j);

}

_arr.push(s);

}

var p = _arr.reduce(function (pre, cur) {

var a = [];

for (var i = 0; i < pre.length; i++) {

for (var j = 0; j < cur.length; j++) {

a.push([].concat(pre[i], cur[j]))

}

return a;

})

console.log(p)

應該可以nlog(n) 時間復雜度,但是不會

let arr = [23,35,23,36,5];

var _arr = [];

for (var i = 0; i < arr.length; i++) {

var s = [];

for (var j = 1; j <= arr[i]; j++) {

s.push(j);

}

_arr.push(s);

}

var p = [];

function f(arr) {

var len = arr.length;

if (len < 2) {

return arr[0];

}

var mid = Math.ceil(len / 2),

left = arr.slice(0, mid),

right = arr.slice(mid);

return z(f(left), f(right));

}

function z(left, right) {

var a = [];

for (var i = 0; i < left.length; i++) {

for (var j = 0; j < right.length; j++) {

a.push([].concat(left[i], right[j]))

}

return p.concat(a);

}

console.log(p)

最后一種效率會高一點

反對回復 2019-03-12

哆啦的時光機

TA貢獻1779條經驗獲得超6個贊

var arr = [2, 2, 3,2];

var curr=[];

for(var i=1;i<=arr.length;i++){

curr.push(1)

}

var result=[];

result.push(curr.concat());

var len=arr.length;

fk:while(true){

var a=curr[len-1]++;

for(var i=len-1;i>=0;i--){

if(curr[i]>arr[i]){

if(i>=1){

curr[i-1]++;

curr[i]=1;

}else{

break fk;

}

var t=curr.concat();

result.push(t);

}

console.log(result);

和一樓的做法不一樣，這個思路是，每次最后一位 +1 ，然后檢查，是不是需要定位了，定位的條件是初始給的數組每個位的值。

反對回復 2019-03-12

忽然笑

TA貢獻1806條經驗獲得超5個贊

如果你最多是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=1

3，表示1,2,3 3種狀態，對應2位二進制，最大值3-1=2

這樣，需要1+1+2共4位二進制數來表示所有組合，其中還需要濾除最高位的2個段的一些情況（2位2進制數其實可以表示4種狀態的），后面注意是低位開始對應

00 0 0，對應1,1,1

00 0 1, 對應2,1,1

00 1 0，對應1,2,1

00 1 1，對應2,2,1

01 0 0，對應1,1,2

01 0 1，對應2,1,2

01 1 0，對應1,2,2

01 1 1，對應2,2,2

10 0 0，對應1,1,3

10 0 1，對應2,1,3

10 1 0，對應1,2,3

10 1 1，對應2,2,3

11 0 0 位段超出不符合

11 0 1 位段超出不符合

11 1 0 位段超出不符合

11 1 1 位段超出不符合

算法思路就介紹到這里，實現其實不是太復雜，不過如果位數太多了（超出語言處理范圍）還是需要分治

這個問題如果真實的規模比較大，還需要考慮空間復雜度和時間復雜度問題，遞歸肯定是不行的，就是轉換遞歸為循環，空間復雜度也不一定好（當然實際情況下也不該由javascript來處理這么大復雜度的問題，但仍需考慮不是）。

這里再給出一個循環的方式

var arr = [2,2,3,2,5];

function MC(inarr,n){

var rt=[];

for(var i=0;i<inarr.length;i++){

for(var j=1;j<=n;j++){

var t=inarr[i].concat();

t.push(j);

rt.push(t)

}

return rt;

}

var mrt=[[]];

for(var i=0;i<arr.length;i++){

mrt=MC(mrt,arr[i]);

}

console.log(mrt);

反對回復 2019-03-12

3 回答
0 關注
685 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

javascript 數組排列組合

javascript 數組排列組合

3 回答

添加回答