All Array Combination in JavaScript

Question

Need all possible combinations of an array including the reverse of a combination too.

Eg:

var b = ['a1','b1','a','b'];

Need combinations as:

a1,b1,a,b
a1b1,a1a,a1b, b1a1,b1a,b1b, ......,
a1b1a,a1b1b,a1ab1,a1bb1,........,
a1b1ab,a1b1ba.....bab1a1

All 64 combinations (if array has 4 elements). I found solution in java using ArrayList and Collection API, but right now I need a pure JavaScript ES5 solution.

I tried the following, but it only provides lesser combinations.

function getCombinations(chars) {
 var result = [];
 var f = function (prefix, chars) {
 for (var i = 0; i < chars.length; i++) {
 result.push(prefix + chars[i]);
 f(prefix + chars[i], chars.slice(i + 1));
 }
 }
 f('', chars);
 return result;
}

• briosheje: Did you check this already? stackoverflow.com/questions/4331092/… How does it happen that you expect 64 values? shouldn't it be 256?
• Akshay Rathnavas: I had already gone through the above link and it mainly deals with multiple arrays.
• mighty_dev: @Bergi But this current question also includes different kinds of permutations.
• גלעד ברקן: @Bergi the question you marked is also not a duplicate since it doesn't include all permutations of the combinations. (I also have a meta warning about moderators unilaterally marking duplicates they have answered themselves.)
• Bergi: @vivek_23 You might be right - the desired results here contain both a1b1 and b1a1, also a1b1ba and bab1a1 which are permutations. Others seem to be missing though.

Answer 1

Let's put your request into words: for each starting element, append all permutations of all combinations of the rest of the elements.

function f(A, comb=[], result=[comb]){
 return A.reduce((acc, a, i) => acc.concat(f(A.slice(0,i).concat(A.slice(i+1)), comb.concat(a))), result);
}
console.log(JSON.stringify(f(['a', 'b', 'c', 'd'])));

• Smytt: I really don't mean to get catty - I think the main purpose of asking questions on StackOverflow (as newbies) is to learn, not to just get the problem solved. So, cutting down the solution to 3 lines might be convenient but it's really heavy on the eyes. A good solution, though, nonetheless.
• גלעד ברקן: @Smytt on the contrary - my answer offers a wonderful opportunity for the OP and others to learn. Can you tell how?
• Smytt: the way you name you variables, using capital letters and incomplete words can be misleading. also, function call within function call - it just needs a lot of dissection to understand what it's doing.
• גלעד ברקן: @Smytt omg. A is one of the most common ways to label an array (virtually every online question lists A[i] as array selections). result means exactly what it is labeled as, and comb is short for "combination" (is that really an issue?). Finally, we have a recursive call and a call to two JavaScript array methods. What are you talking about? It sounds to me like you take an issue with having to learn new things.
• Smytt: No need to get defensive. As I said, I only shared an opinion.

Answer 2

a somewhat simple recursion will deal with this issue. Check it out:

function getCombinations(chars) {
 let combinations = [];
 chars.forEach((char, i) => {
 let word = '';
 buildWord(word + char, [i], chars, combinations)
 });
 return combinations;
}
function buildWord(word, usedIndexes, chars, combinations) {
 combinations.push(word);
 chars.forEach((char, i) => {
 if (usedIndexes.indexOf(i) === -1) {
 let newUsedIndexesArray = Array.from(usedIndexes);
 newUsedIndexesArray.push(i);
 buildWord(word + char, newUsedIndexesArray, chars, combinations)
 }
 });
}
console.log('Total: ' + getCombinations(['a1', 'b1', 'a', 'b']).length)
console.log(getCombinations(['a1', 'b1', 'a', 'b']))

• Smytt: Yes. I edited it. I was under the assumption that the permutations need to include all 4 members. so This works now - permutations without repetition of members
• גלעד ברקן: Is this JavaScript ES5?
• Smytt: Just edited it to fit your ES5 requirement. Both the spread operator (...) and Array.prototype.includes come later and could not be used. As you see, the code gets a tad heavier on the eye.

Answer 3

Below is an iterative approach. We go from permutation length of 1 till length(no. of characters in the given chars) and generate all possible combinations for each length. We maintain a set to avoid duplicates and isValidPermutation() check to see whether a combination is possible from given set of chars to avoid invalid combinations.

function getCombinations(chars) {
 if (chars === undefined || chars === null || chars.length === 0) return [];
 var final_result = [];
 var temp_result_1 = chars.slice();
 var set = {};
 /* for initial set of elements */
 for (var i = 0; i < temp_result_1.length; ++i) {
 if (set[temp_result_1[i]] === undefined) {
 set[temp_result_1[i]] = true;
 final_result.push(temp_result_1[i]);
 }
 }
 /* go from 2 to length(since length 1 is captured above) to get all permutations of combinations */
 for (var len = 2; len <= chars.length; ++len) {
 var temp_result_2 = [];
 for (var i = 0; i < chars.length; ++i) {
 for (var j = 0; j < temp_result_1.length; ++j) {
 var current_permutation = chars[i] + "," + temp_result_1[j];
 if (set[current_permutation] === undefined && isValidPermutation(current_permutation, chars)) {
 temp_result_2.push(current_permutation);
 set[current_permutation] = true;
 }
 }
 }
 temp_result_1 = temp_result_2;
 final_result = final_result.concat(temp_result_1);
 }
 return final_result.map((each) => each.split(",").join(""));
}
/* to check if actually a combination is true and possible from current set of chars */
function isValidPermutation(current_permutation, chars) {
 var hash = {};
 current_permutation = current_permutation.split(",");
 for (var i = 0; i < chars.length; ++i) {
 if (hash[chars[i]] === undefined) hash[chars[i]] = 0;
 hash[chars[i]]++;
 }
 for (var i = 0; i < current_permutation.length; ++i) {
 hash[current_permutation[i]]--;
 if (hash[current_permutation[i]] < 0) return false;
 }
 return true;
}
var b = ['a1', 'b1', 'a', 'b'];
console.log(getCombinations(b));

Since you need a ECMAScript 5 solution, you change the last line

return final_result.map((each) => each.split(",").join(""));

to

 for(var i=0;i<final_result.length;++i){
 final_result[i] = final_result[i].split(",").join("");
 }
 return final_result;