Lets Explore combinations to find all r length combinations for array of
length n. e.g. Find all 2 length combinations for array
["apple", "banana", "lemon","mango","cashew","litchi","durian"];
Solution 1:
function hasElement(ar, val) {
var hash = {};
for (var i = 0; i < ar.length; i += 1) {
hash[ar[i]] = i;
}
if (hash.hasOwnProperty(val)) {
return true;
} else {
return false;
}
}
function getCombination(array, r) {
let result = [];
if (r == array.length) {
result.push(array);
return result;
} else if (r == 0) {
return [[]];
} else if (r == 1) {
array.forEach((element) => {
result.push([element]);
});
return result;
} else {
let iThElement;
for (let i = 0; i < array.length; i++) {
iThElement = array[i];
let remainingElements = array.filter((elem) => {
return elem != iThElement;
});
let intermediateResult = getCombination(remainingElements, r - 1);
intermediateResult.forEach((elem) => {
elem.push(iThElement);
//sort
elem = elem.sort((a, b) => {
if (a == b) {
return 0;
} else if (a > b) {
return 1;
} else {
return -1;
}
});
//find if element is preexisting in result array
if (hasElement(result, elem) == false) {
result.push(elem);
}
});
}
return result;
}
}
const array = [
"apple",
"banana",
"lemon",
"mango",
"cashew",
"litchi",
"durian",
];
let result = getCombination(array, 2);
console.log("result:", result);
console.log("result length:", result.length);
Output:
result: [
[ 'apple', 'banana' ], [ 'apple', 'lemon' ],
[ 'apple', 'mango' ], [ 'apple', 'cashew' ],
[ 'apple', 'litchi' ], [ 'apple', 'durian' ],
[ 'banana', 'lemon' ], [ 'banana', 'mango' ],
[ 'banana', 'cashew' ], [ 'banana', 'litchi' ],
[ 'banana', 'durian' ], [ 'lemon', 'mango' ],
[ 'cashew', 'lemon' ], [ 'lemon', 'litchi' ],
[ 'durian', 'lemon' ], [ 'cashew', 'mango' ],
[ 'litchi', 'mango' ], [ 'durian', 'mango' ],
[ 'cashew', 'litchi' ], [ 'cashew', 'durian' ],
[ 'durian', 'litchi' ]
]
result length: 21
Solution 2:
This Solution is compact & nice to remember.
function getCombination(input, chooseBasketSize) {
let results = [];
function innerFunction(startIndex, result) {
if (result.length === chooseBasketSize) {
let intermediateResult = result.map((elem) => {
return input[elem - 1];
});
results.push(intermediateResult);
return result;
} else {
for (let i = startIndex; i < input.length + 1; i++) {
result.push(i);
innerFunction(i + 1, result);
result.pop();
}
}
}
innerFunction(1, []);
return results;
}
const input = ["apple", "banana", "lemon", "mango"];
let results = getCombination(input, 3);
console.log("results:", results);
Output:
results: [
[ 'apple', 'banana', 'lemon' ],
[ 'apple', 'banana', 'mango' ],
[ 'apple', 'lemon', 'mango' ],
[ 'banana', 'lemon', 'mango' ]
]
Solution 3:
function hasElement(ar, val) {
var hash = {};
for (var i = 0; i < ar.length; i += 1) {
hash[ar[i]] = i;
}
if (hash.hasOwnProperty(val)) {
return true;
} else {
return false;
}
}
function getCombination(array, r, startIndex) {
let result = {};
let combinations = [];
if (r == array.length) {
combinations = [];
array = array.sort((a, b) => {
if (a == b) {
return 0;
} else if (a > b) {
return 1;
} else {
return -1;
}
});
combinations.push(array);
result[r] = combinations;
return result;
} else if (r == 0) {
return [[]];
} else if (r == 1) {
array.forEach((element) => {
result.push([element]);
});
return result;
} else {
let intermediateResult = getCombination(array, r + 1, 0); //3 th
result = { ...intermediateResult };
combinations = [];
let previousResult = intermediateResult[r + 1];
for (let j = 0; j < previousResult.length; j++) {
for (let k = 0; k < previousResult[j].length; k++) {
let reduced = previousResult[j].filter((elem, index) => {
if (index != k) {
return true;
}
});
reduced = reduced.sort((a, b) => {
if (a == b) {
return 0;
} else if (a > b) {
return 1;
} else {
return -1;
}
});
//find if element is preexisting in result array
if (hasElement(combinations, reduced) == false) {
combinations.push(reduced);
}
}
}
result[r] = combinations;
return result;
}
return result;
}
const array = ["apple", "banana", "lemon", "mango", "cashew","durian"];
let result = getCombination(array, 3, 0);
console.log("result:", result);
console.log("result:", result[3].length);
Output:
result: {
'3': [
[ 'durian', 'lemon', 'mango' ],
[ 'cashew', 'lemon', 'mango' ],
[ 'cashew', 'durian', 'mango' ],
[ 'cashew', 'durian', 'lemon' ],
[ 'banana', 'lemon', 'mango' ],
[ 'banana', 'durian', 'mango' ],
[ 'banana', 'durian', 'lemon' ],
[ 'banana', 'cashew', 'mango' ],
[ 'banana', 'cashew', 'lemon' ],
[ 'banana', 'cashew', 'durian' ],
[ 'apple', 'lemon', 'mango' ],
[ 'apple', 'durian', 'mango' ],
[ 'apple', 'durian', 'lemon' ],
[ 'apple', 'cashew', 'mango' ],
[ 'apple', 'cashew', 'lemon' ],
[ 'apple', 'cashew', 'durian' ],
[ 'apple', 'banana', 'mango' ],
[ 'apple', 'banana', 'lemon' ],
[ 'apple', 'banana', 'durian' ],
[ 'apple', 'banana', 'cashew' ]
],
'4': [
[ 'cashew', 'durian', 'lemon', 'mango' ],
[ 'banana', 'durian', 'lemon', 'mango' ],
[ 'banana', 'cashew', 'lemon', 'mango' ],
[ 'banana', 'cashew', 'durian', 'mango' ],
[ 'banana', 'cashew', 'durian', 'lemon' ],
[ 'apple', 'durian', 'lemon', 'mango' ],
[ 'apple', 'cashew', 'lemon', 'mango' ],
[ 'apple', 'cashew', 'durian', 'mango' ],
[ 'apple', 'cashew', 'durian', 'lemon' ],
[ 'apple', 'banana', 'lemon', 'mango' ],
[ 'apple', 'banana', 'durian', 'mango' ],
[ 'apple', 'banana', 'durian', 'lemon' ],
[ 'apple', 'banana', 'cashew', 'mango' ],
[ 'apple', 'banana', 'cashew', 'lemon' ],
[ 'apple', 'banana', 'cashew', 'durian' ]
],
'5': [
[ 'banana', 'cashew', 'durian', 'lemon', 'mango' ],
[ 'apple', 'cashew', 'durian', 'lemon', 'mango' ],
[ 'apple', 'banana', 'durian', 'lemon', 'mango' ],
[ 'apple', 'banana', 'cashew', 'lemon', 'mango' ],
[ 'apple', 'banana', 'cashew', 'durian', 'mango' ],
[ 'apple', 'banana', 'cashew', 'durian', 'lemon' ]
],
'6': [ [ 'apple', 'banana', 'cashew', 'durian', 'lemon', 'mango' ] ]
}
result: 20
Solution 4 (Without Recursion)
function hasElement(ar, val) {
var hash = {};
for (var i = 0; i < ar.length; i += 1) {
hash[ar[i]] = i;
}
if (hash.hasOwnProperty(val)) {
return true;
} else {
return false;
}
}
function getCombination(input, r) {
if (input.length == r) {
return [input];
} else if (r == 1) {
return input.reduce((accumulator, element) => {
accumulator.push([element]);
return accumulator;
}, []);
} else {
let result = [[[]]];
while (result.length != r + 1) {
let iLengthArray = [];
for (let element of input) {
let lastArray = result[result.length - 1];
for (let i = 0; i < lastArray.length; i++) {
if (!lastArray[i].includes(element)) {
let newElement = [...lastArray[i], element];
newElement = newElement.sort((a, b) => {
if (a == b) {
return 0;
} else if (a < b) {
return -1;
} else {
return 1;
}
});
if (!hasElement(iLengthArray, newElement)) {
iLengthArray.push(newElement);
}
}
}
}
result.push(iLengthArray);
}
return result[r];
}
}
const input = ["apple", "banana", "lemon", "mango", "cashew"];
let results = getCombination(input, 2);
console.log("results:", results);
Output:
results: [
[ 'apple', 'banana' ],
[ 'apple', 'lemon' ],
[ 'apple', 'mango' ],
[ 'apple', 'cashew' ],
[ 'banana', 'lemon' ],
[ 'banana', 'mango' ],
[ 'banana', 'cashew' ],
[ 'lemon', 'mango' ],
[ 'cashew', 'lemon' ],
[ 'cashew', 'mango' ]
]
Solution 5: Using ordering of indexes
function outerFunction(wordArray, indexArray, chooseBasketSize) {
let results = {};
function getCombination(indexArray, chooseBasketSize) {
if (chooseBasketSize == 1) {
let sizeOne = indexArray.reduce((acc, elem) => {
acc.push([elem]);
return acc;
}, []);
results[1] = { combinations: sizeOne };
return results;
} else if (chooseBasketSize == indexArray.length) {
results[chooseBasketSize] = { combinations: [indexArray] };
return results;
} else {
let intermediateResult = getCombination(indexArray, chooseBasketSize - 1);
let loopOver = intermediateResult[chooseBasketSize - 1].combinations;
let newElement = [];
for (let i = 0; i < indexArray.length; i++) {
for (let j = 0; j < loopOver.length; j++) {
let lastElement = loopOver[j][loopOver[j].length - 1];
if (lastElement < indexArray[i]) {
let im = [...loopOver[j], indexArray[i]];
newElement.push(im);
}
}
}
results[chooseBasketSize] = { combinations: newElement };
return results;
}
}
//result json object
let combinationBasedOnIndexes = getCombination(indexArray, chooseBasketSize);
//extract exactly cmbination array from json object
combinationBasedOnIndexes =
combinationBasedOnIndexes[chooseBasketSize].combinations;
//replace indexes with actual words
let combinationBasedOnWords = combinationBasedOnIndexes.map(
(outerElement) => {
return outerElement.map((innerElement) => {
return wordArray[innerElement];
});
}
);
return combinationBasedOnWords;
}
const wordArray = ["apple", "banana", "lemon", "mango", "durian", "cachew"];
//0 based index array
const indexArray = Array.from(Array(wordArray.length).keys());
let result = outerFunction(wordArray, indexArray, 4);
console.log("results:", result);
Output:
results: [
[ 'apple', 'banana', 'lemon', 'mango' ],
[ 'apple', 'banana', 'lemon', 'durian' ],
[ 'apple', 'banana', 'mango', 'durian' ],
[ 'apple', 'lemon', 'mango', 'durian' ],
[ 'banana', 'lemon', 'mango', 'durian' ],
[ 'apple', 'banana', 'lemon', 'cachew' ],
[ 'apple', 'banana', 'mango', 'cachew' ],
[ 'apple', 'lemon', 'mango', 'cachew' ],
[ 'banana', 'lemon', 'mango', 'cachew' ],
[ 'apple', 'banana', 'durian', 'cachew' ],
[ 'apple', 'lemon', 'durian', 'cachew' ],
[ 'banana', 'lemon', 'durian', 'cachew' ],
[ 'apple', 'mango', 'durian', 'cachew' ],
[ 'banana', 'mango', 'durian', 'cachew' ],
[ 'lemon', 'mango', 'durian', 'cachew' ]
]
Solution 6 :Previous solution modified directly return word array
combinations rather than map over index based combination array
function outerFunction(wordArray, indexArray, chooseBasketSize) {
let results = {};
function getCombination(indexArray, chooseBasketSize) {
if (chooseBasketSize == 1) {
let sizeOneWords = wordArray.reduce((acc, elem) => {
acc.push([elem]);
return acc;
}, []);
let sizeOneIndexes = indexArray.reduce((acc, elem) => {
acc.push([elem]);
return acc;
}, []);
results[1] = { combinationBasedOnIndexes: sizeOneIndexes,combinationBasedOnWord:sizeOneWords };
return results;
} else if (chooseBasketSize == wordArray.length) {
results[chooseBasketSize] = { combinationBasedOnIndexes:[indexArray], combinationBasedOnWord: [wordArray] };
return results;
} else {
let intermediateResult = getCombination(indexArray, chooseBasketSize - 1);
let loopOverIBasedOnIndexes = intermediateResult[chooseBasketSize - 1].combinationBasedOnIndexes;
let loopOverBasedOnWords = intermediateResult[chooseBasketSize - 1].combinationBasedOnWord;
let newElementBasedOnIndexes = [];
let newElementBasedOnWords = [];
for (let i = 0; i < indexArray.length; i++) {
for (let j = 0; j < loopOverIBasedOnIndexes.length; j++) {
let lastElement = loopOverIBasedOnIndexes[j][loopOverIBasedOnIndexes[j].length - 1];
if (lastElement < indexArray[i]) {
newElementBasedOnIndexes.push([...loopOverIBasedOnIndexes[j], indexArray[i]]);
newElementBasedOnWords.push([...loopOverBasedOnWords[j], wordArray[i]]);
}
}
}
results[chooseBasketSize] = { combinationBasedOnIndexes: newElementBasedOnIndexes ,
combinationBasedOnWord:newElementBasedOnWords };
return results;
}
}
let combinations = getCombination(indexArray, chooseBasketSize); //result json object
let combinationBasedOnWord = combinations[chooseBasketSize].combinationBasedOnWord
return combinationBasedOnWord;
}
const wordArray = ["apple", "banana", "lemon", "mango", "durian", "cachew"];
const indexArray = Array.from(Array(wordArray.length).keys()); //0 based index array
let result = outerFunction(wordArray, indexArray, 6);
console.log("results:", result);
Output:
results: [ [ 'apple', 'banana', 'lemon', 'mango', 'durian', 'cachew' ] ]
No comments:
Post a Comment