# In how many different ways can a group of 9 people be divided into 3 groups, with each group containing 3 people?

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?

1. Gather all the permutations from the given array.
2. 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.

• I have absolutely no idea what the program is supposed to do. Finding some kind of combinations is as far as I understood. The rest is in fog. Do you have any formal specification for the problem? Or at least can you show a complete example output and describe why it is what it is? Jul 21, 2021 at 5:00
• According to the title: k is the size (with of?) the array. According to the 1st sentence: k is the size of the groups (each group in the array?). .. which would mean there is exactly one group in the array (which is silly). It feels like there's a fun problem here and I had hoped I could reverse engineer the problem statement into something sensible, but somehow the description managed to become utterly unintelligible (to me). Please rephrase the question accurately because it still seems something that could be interesting. Jul 21, 2021 at 15:38
• @slepic I've updated the question. Please consider it. Jul 22, 2021 at 4:52
• @KoenAIS I've updated the question. Please consider it. Jul 22, 2021 at 4:52
• Your update is great, well done! Here's my approach (it doesn't need to generate all permutations or checks for double counts). The crux is to distinguish between 3C2 cases: 1) all first 3 persons in the 1st group, 2) 1st person in the 1st group, the next two both in the 2nd, 3) 1st person the the 1st group, 2nd person in in the 2nd group and 3rd person in the 3rd group. These cases can't yield double-counts, eliminating the need to check. After this is it just becomes a recursive problem with independent subproblems. If this is not fully clear I can elaborate and make it an answer. Jul 22, 2021 at 13:29

## 1 Answer

The problem is metaphorically to assign 9 persons to 9 seats (each person their own seat). The seats come in groups of 3.

There are 362880 seating arrangements, but only 280 canonical ones because:

• A) Reseating the persons within one group doesn't essentially change the arrangement.

• B) Reordering the groups also doesn't essentially change the arrangement.

The idea is to generate only the canonical permutations, so let's express A and B a bit more precise by imposing an ordering. Let P[1..9] be a permutation of [1..9] (a seating arrangement). It is canonical if:

• A) P[1..3], P[4..6] and P[7..9] are sorted
• B) P[1] < P[4] < P[7]

Generating only the permutations that satisfy A and B avoids the overhead of generating (and checking) 362880 - 280 "duplicates". An easy way to do this is to recursively assign persons to seats in lexicographic order while keeping a close eye on A and B.

That's roughly the algorithm done. All that's left is to pick a language and implement it. I chose Java:

N = 0;
boolean[] needsASeat = new boolean[10];
Arrays.fill(needsASeat, true);
seatPersons(0, needsASeat, new int[9]);
if (N != 280) throw new SanityCheckFailed();


where

void seatPersons(int seatIdx, boolean[] needsASeat, int[] seatingArrangement) {
if (seatIdx < 9) { // this seat is still unoccupied
// pick each person who still needs a seat and is allowed to sit here (i.e., without violating A and B)
int minPersonIdx;
if (seatIdx % 3 != 0) // A is at stake
minPersonIdx = seatingArrangement[seatIdx - 1] + 1;
else if (seatIdx != 0) // B is at stake
minPersonIdx = seatingArrangement[seatIdx - 3] + 1;
else
minPersonIdx = 1; // this is also the maximum, but there's no need for tricky optimizations
for (int personIdx = minPersonIdx; personIdx <= 9; personIdx++) if (needsASeat[personIdx]) {
seatingArrangement[seatIdx] = personIdx;
needsASeat[personIdx] = false;
seatPersons(seatIdx + 1, needsASeat, seatingArrangement);
needsASeat[personIdx] = true;
seatingArrangement[seatIdx] = 0;
}
} else { // all seats occupied
// do sth with the arrangement
N++;
}
}


PS: an earlier version of this answer gives a more efficient implementation by starting in initial configurations in which first seats of groups are already occupied. In realized afterwards I had made that optimization unconsciously without even explaining why it works and why it is faster. This new version is significantly slower but it explains the algorithm clearer and is still must faster than the "check all permutations"-approach.

Never mind. Here's that optimized version:

N = 0;
// partition the set of canonical permutations by "pre-seating" 1, 2 and 3:
int[][] startingPoints = new int[][]{
{1, 2, 3,   4, 0, 0,   0, 0, 0}, // 1,2,3 together
{1, 2, 0,   3, 0, 0,   0, 0, 0}, // 1,2 together, 3 alone
{1, 0, 0,   2, 3, 0,   0, 0, 0}, // 1 alone, 2,3 together
{1, 3, 0,   2, 0, 0,   0, 0, 0}, // 2 alone, 1,3 together
{1, 0, 0,   2, 0, 0,   3, 0, 0}  // each alone
};
boolean[] needsASeat = new boolean[10];
for (int[] startingPoint : startingPoints) {
Arrays.fill(needsASeat, true);
for (int p : startingPoint) needsASeat[p] = false;
seatPersons(0, needsASeat, startingPoint);
}
if (N != 280) throw new SanityCheckFailed();


where

void seatPersons(int seatIdx, boolean[] needsASeat, int[] seatingArrangement) {
while (seatIdx < 9 && seatingArrangement[seatIdx] != 0) seatIdx++; // skip occupied seats
if (seatIdx < 9) {
int minPersonIdx = seatIdx % 3 != 0 ? seatingArrangement[seatIdx - 1] + 1 : 4; // B is never at stake thanks to the initial configuration
for (int personIdx = minPersonIdx; personIdx <= 9; personIdx++) if (needsASeat[personIdx]) {
seatingArrangement[seatIdx] = personIdx;
needsASeat[personIdx] = false;
seatPersons(seatIdx + 1, needsASeat, seatingArrangement);
needsASeat[personIdx] = true;
seatingArrangement[seatIdx] = 0;
}
} else {
// do sth with the arrangement
N++;
}
}