Need all possible binations of an array including the reverse of a bination too.
Eg:
var b = ['a1','b1','a','b'];
Need binations as:
a1,b1,a,b
a1b1,a1a,a1b, b1a1,b1a,b1b, ......,
a1b1a,a1b1b,a1ab1,a1bb1,........,
a1b1ab,a1b1ba.....bab1a1
All 64 binations (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 binations.
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;
}
Need all possible binations of an array including the reverse of a bination too.
Eg:
var b = ['a1','b1','a','b'];
Need binations as:
a1,b1,a,b
a1b1,a1a,a1b, b1a1,b1a,b1b, ......,
a1b1a,a1b1b,a1ab1,a1bb1,........,
a1b1ab,a1b1ba.....bab1a1
All 64 binations (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 binations.
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;
}
Share
Improve this question
edited Jun 18, 2019 at 21:54
Prune
77.9k14 gold badges62 silver badges83 bronze badges
asked Jun 18, 2019 at 12:31
Akshay RathnavasAkshay Rathnavas
3585 silver badges16 bronze badges
14
- Did you check this already? stackoverflow./questions/4331092/… How does it happen that you expect 64 values? shouldn't it be 256? – briosheje Commented Jun 18, 2019 at 12:34
- I had already gone through the above link and it mainly deals with multiple arrays. – Akshay Rathnavas Commented Jun 18, 2019 at 12:50
- @Bergi But this current question also includes different kinds of permutations. – nice_dev Commented Jun 18, 2019 at 14:31
- 2 @Bergi the question you marked is also not a duplicate since it doesn't include all permutations of the binations. (I also have a meta warning about moderators unilaterally marking duplicates they have answered themselves.) – גלעד ברקן Commented Jun 18, 2019 at 14:38
-
1
@vivek_23 You might be right - the desired results here contain both
a1b1
andb1a1
, alsoa1b1ba
andbab1a1
which are permutations. Others seem to be missing though. – Bergi Commented Jun 18, 2019 at 14:45
3 Answers
Reset to default 5Let's put your request into words: for each starting element, append all permutations of all binations of the rest of the elements.
function f(A, b=[], result=[b]){
return A.reduce((acc, a, i) => acc.concat(f(A.slice(0,i).concat(A.slice(i+1)), b.concat(a))), result);
}
console.log(JSON.stringify(f(['a', 'b', 'c', 'd'])));
a somewhat simple recursion will deal with this issue. Check it out:
function getCombinations(chars) {
let binations = [];
chars.forEach((char, i) => {
let word = '';
buildWord(word + char, [i], chars, binations)
});
return binations;
}
function buildWord(word, usedIndexes, chars, binations) {
binations.push(word);
chars.forEach((char, i) => {
if (usedIndexes.indexOf(i) === -1) {
let newUsedIndexesArray = Array.from(usedIndexes);
newUsedIndexesArray.push(i);
buildWord(word + char, newUsedIndexesArray, chars, binations)
}
});
}
console.log('Total: ' + getCombinations(['a1', 'b1', 'a', 'b']).length)
console.log(getCombinations(['a1', 'b1', 'a', 'b']))
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 binations for each length.
We maintain a set
to avoid duplicates and isValidPermutation()
check to see whether a bination is possible from given set of chars
to avoid invalid binations.
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 binations */
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 bination 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;