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

Question

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.

Answer 1

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) min(P[1..3]) < min(P[4..6]) < min(P[7..9])

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 = Math.min(Math.min(seatingArrangement[seatIdx - 1], seatingArrangement[seatIdx - 2]), 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++;
    }
}