To divide 9 persons into 3 groups, when the ordering of groups is not important can be done in
(9C3 * 6C3 * 3C3) / (3!) = 280 ways
Here, we divide by (3!) because the ordering of 3 groups is not important
What I did?
- Gather all the permutations from the given array.
- While grouping the combinations, discard the hands that has been traversed.
function generatePermutations(array, size) {
const result = [];
function permutation(target, i) {
if (target.length === size) {
result.push(target);
return;
}
if (i + 1 > array.length) return;
permutation(target.concat(array[i]), i + 1);
permutation(target, i + 1);
}
permutation([], 0);
return result;
}
function createCombinationsBag() {
let travsedCombinationIdentity = 0;
const traversedCombinationMap = new Map();
let travsedCombinationsIdentity = 0;
const traversedCombinationsMap = new Map();
function getCombinationId(arrNums) {
const reordered = arrNums.slice().sort().join("");
const combinationId = traversedCombinationMap.get(reordered);
if (combinationId) return combinationId;
travsedCombinationIdentity++;
traversedCombinationMap.set(reordered, travsedCombinationIdentity);
return travsedCombinationIdentity;
}
function isCombinationTraversed(firstId, secondId, thirdId) {
const reordered = [firstId, secondId, thirdId].sort().join("");
const combinationsId = traversedCombinationsMap.get(reordered);
if (combinationsId) return true;
travsedCombinationsIdentity++;
traversedCombinationsMap.set(reordered, travsedCombinationsIdentity);
return false;
}
function has(first, second, third) {
return isCombinationTraversed(
getCombinationId(first),
getCombinationId(second),
getCombinationId(third)
);
}
return { has };
}
export function generateCombinations(array, size) {
const allPermutations = generatePermutations(array, size);
const combinations = [];
const CombinationBag = createCombinationsBag();
for (let i = 0; i < allPermutations.length; i++) {
const first = allPermutations[i];
for (let j = 0; j < allPermutations.length; j++) {
const second = allPermutations[j];
const firstSecond = first.concat(second);
if (firstSecond.length !== new Set(firstSecond).size) continue;
for (let k = 0; k < allPermutations.length; k++) {
const third = allPermutations[k];
const maybeCombination = firstSecond.concat(third);
const combinationSet = new Set(maybeCombination);
if (maybeCombination.length === combinationSet.size) {
if (CombinationBag.has(first, second, third)) continue;
combinations.push(maybeCombination);
}
}
}
}
return combinations;
}
console.log(generateCombinations([0, 1, 2, 3, 4, 5, 6, 7, 8], 3).length); // 280
Is there a better and optimize way to do this?
Rather than finding all the permutations of group and then looping over them, could there be a solution where we could reach to solution much quicker than this.