JAVASCRIPT算法（2）

AnthonyHan 發(fā)布于2019-08-21 17:51 / 2589人閱讀

摘要：前面兩個(gè)數(shù)組已經(jīng)完成了排列組合，結(jié)果在中，所以替換掉。偶然看到一個(gè)求字符串內(nèi)字符全排列的算法比如給定一個(gè)字符串得出的結(jié)果是該方法是通過(guò)遞歸完成的。加上這一行，起到無(wú)重復(fù)字母的效果在網(wǎng)上看了很多算法，學(xué)習(xí)了很多。

幾個(gè)數(shù)組元素的排列組合問(wèn)題。比如["A","B"],["C","D","E"],["F","G"]，其排列組合的結(jié)果是["A","C","F"],["A","C","G"],["A","D","F"],......,["B","E","F"],["B","E","G"]，共有2x3x2=12種結(jié)果，那么，如何用程序?qū)崿F(xiàn)。

簡(jiǎn)單的思路就是先把前面兩個(gè)數(shù)組的元素做排列組合，產(chǎn)生的新數(shù)組再和后面的數(shù)組做排列組合，始終是在做兩個(gè)數(shù)組的排列組合操作。

function sku(arr){
    if(arr.length<1) return null;
    if(arr.length<2) return arr[0];
    var result=[];
    var firstArr=arr[0];
    for(var i = 0 ; i < firstArr.length ; i ++){ //這里是將第一個(gè)數(shù)組里面的元素變成數(shù)組，方便后續(xù)進(jìn)行concat操作。
        result.push([firstArr[i]]);
    }
    arr.splice(0,1,result);
    while(arr.length>1){
        var targetArr=arr[0];   
        var nextArr=arr[1];
        var result=[];
        for(var i = 0 ; i < targetArr.length; i ++){//進(jìn)行排列組合
            for(var j = 0 ; j < nextArr.length; j ++){
               var tmp=([].concat(targetArr[i]));  //將數(shù)據(jù)復(fù)制到新的數(shù)組里面，因?yàn)楹罄m(xù)targetArr[i]還會(huì)被用到。不能直接更改targetArr[i]這個(gè)數(shù)組。
               tmp.push(nextArr[j]);//
               result.push(tmp);
            }
        }
        arr.splice(0,2,result);//前面兩個(gè)數(shù)組已經(jīng)完成了排列組合，結(jié)果在result中，所以替換掉。
    }
 }

以arr=[["A","B"],["C","D","E"],["F","G"]]作為輸入。

 for(var i = 0 ; i < firstArr.length ; i ++){ //這里是將第一個(gè)數(shù)組里面的元素變成數(shù)組，方便后續(xù)進(jìn)行concat操作。
        result.push([firstArr[i]]);
    }

arr的結(jié)果就變成了[[["A"],["B"]],["C","D","E"],["F","G"]].
然后經(jīng)過(guò)第一次循環(huán)，將[["A"],["B"]],["C","D","E"]兩個(gè)數(shù)組合并，
變成了result這個(gè)數(shù)組的內(nèi)容是[["A","C"],["A","D"],["A","E"],["B","C"],["B","D"],["B","E"]].

arr.splice(0,2,result);

將合并后的數(shù)組去除，然后將合并的結(jié)果放到原數(shù)組列表里面，數(shù)組長(zhǎng)度-1，當(dāng)原數(shù)組只有一個(gè)元素時(shí)，就是最終結(jié)果。

偶然看到一個(gè)求字符串內(nèi)字符全排列的算法

比如給定一個(gè)字符串"abc",得出的結(jié)果是abc,acb,bac,bca,cab,cba.
該方法是通過(guò)遞歸完成的。

var result = [];
function permutations(str){
    var arr= str.split("");
    helper(arr,0,[]);
    return result;
}
function helper(arr,index,list){
    if(index === arr.length){
        result.push(list.join(""));
        return;
    }
    for(var i = 0;i
大意是指每次從原數(shù)組里面選擇一個(gè)目標(biāo)數(shù)組里面沒(méi)有的字符串，直到目標(biāo)數(shù)組長(zhǎng)度和原數(shù)組一樣，然后做一個(gè)join就得出了結(jié)果。
然后我發(fā)現(xiàn)我上面的方法也能達(dá)成這個(gè)目的，只不過(guò)要構(gòu)建字符串長(zhǎng)度這么多的數(shù)組。
每個(gè)數(shù)組的內(nèi)容都一樣，就是字符串split("")以后的結(jié)果。
然后為了保證不重復(fù)，可以把for循環(huán)中加一句。
     for(var i = 0 ; i < targetArr.length; i ++){
            for(var j = 0 ; j < nextArr.length; j ++){
               var tmp=([].concat(targetArr[i]));  
               if(tmp.indexOf(nextArr[j])!=-1) continue;  //加上這一行，起到無(wú)重復(fù)字母的效果
               tmp.push(nextArr[j]);
               result.push(tmp);
            }
        }
在網(wǎng)上看了很多算法，學(xué)習(xí)了很多。有對(duì)的，也有錯(cuò)的；有的簡(jiǎn)單有效，有的瘋狂繞圈。有時(shí)候覺(jué)得高深莫測(cè)，看懂了以后發(fā)現(xiàn)完全沒(méi)必要。還是自己試試。