# javascript – combination of number from an given array with of size k where ordering of the groups should not be repeated

We need to derive a combination of groups of size `k` where the ordering of numbers within k doesn’t get repeated as well as the ordering of those groups within the combination doesn’t repeat either

Allow me to explain the question

Example :- generateCombinations((0, 1, 2, 3, 4, 5, 6, 7, 8), 3);

We need to derive multiple combinations from the array `(0, 1, 2, 3, 4, 6, 7, 8)`consisting of three digits.

``````(0, 2, 3) === (3, 2, 0)
(8, 5, 6) === (6, 8, 5)
``````

Furthermore, the combinations of these group shouldn’t repeat within a combination

``````(0, 2, 3, 5, 6, 7, 8, 1, 4) === (2, 3, 0, 5, 7, 6, 4, 1, 8)

where
(0, 2, 3) === (2, 3, 0)
(5, 6, 7) === (5, 7, 6)
(8, 1, 4) === (4, 1, 8)
``````

## What I did?

1. Gather all the permutations from the given array.
2. While grouping the combinations, discard the groups 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 and then looping over them, could there be a solution where we could reach to solution much quicker than this.

Posted on Categories Articles