生成所提供单词的所有组合和排列

Question

如何使用javascript获得所有可能的单词组合？

例如 - 如果我有 3 个词 Apple , Banana , Orange

我需要这些词的所有独特组合，即

comb1 = Apple ;
Comb2 = Banana ;
Comb3 = Orange ;
Comb4 = Apple + Banana ;
Comb5 = Apple + Orange ;
Comb6 = Banana + Orange ;
Comb7 = Banana + Apple ;
Comb8 = Orange + Apple ;
Comb9 = Orange + Banana ;
Comb10 = Apple + Banana + Orange ;
Comb11 = Apple + Orange + Banana ;
Comb12 = Banana + Orange + Apple ;
Comb13 = Banana + Apple + Orange ;
Comb14 = Orange + Apple + Banana ;
Comb15 = Orange + Banana + Apple ;

我需要这是动态的，即根据提供的单词数生成组合。

我尝试过类似下面的代码，但没有得到预期的结果

var permArr = [],result=[],aa=[],
  usedChars = [];
 var comb =['a', 'b','c'];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  //return permArr
};

for(var i=0;i<comb.length;i++){
    aa=[];
    for(var j=0;j<=i;j++)

    {
        aa.push(comb[j]);
    }
    permute(aa);

}


FResult = JSON.stringify(permArr);

代码在输出下方返回，这是未完成的输出。

[["a"],["a","b"],["b","a"],["a","b","c"],["a","c","b"],["b","a","c"],["b","c","a"],["c","a","b"],["c","b","a"]]

我的代码错过了 [b,c] 和 [a,c] 和 [b] 和 [c] 的排列。我的 permute() 函数工作正常。只需要提供正确的组合。

谢谢！

Answer 1

一种更有效的生成排列的方法

 function permutations(k, curr_perm, included_items_hash){
     if(k==0){
        perm.push(curr_perm);
        return;
     }
     
     
     for(let i=0; i<items.length; i++){

        // so that we do not repeat the item, using an array here makes it O(1) operation
        if(!included_items_hash[i]){
            included_items_hash[i] = true;
            permutations(k-1, curr_perm+items[i], included_items_hash);
            included_items_hash[i] = false;
        }
        
     }
 }

let items = ["a","b","c"];
let perm = [];

// for generating different lengths of permutations
for(let i=0; i<items.length; i++){
    permutations(items.length-i, "", []);
}

console.log(perm);