Generate all combination and permutation of supplied word

user_14080218 0
Viewed 429

How can I get all possible combination of words using javascript?

For example - if I have 3 word Apple , Banana , Orange

I need all unique combinations of those words I.e.

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 ;

I need this to be dynamic I.e. combination to be generated depending upon a no of words supplied.

I have tried something like below code but did not get expected result

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

Code return below output which is not completed output.

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

My code missed to permutation with [b,c] and [a,c] and [b] and [c]. My permute() function work properly. Just need to supply correct combination.

Thanks!

permutation algorithm javascript
1 Answers

A more efficient way of generating the permutations

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

user_83074560
Related