1
\$\begingroup\$

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.

New contributor
Prateek Thapa is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
8
  • \$\begingroup\$ 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? \$\endgroup\$ – slepic 2 days ago
  • \$\begingroup\$ 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. \$\endgroup\$ – Koen AIS 2 days ago
  • \$\begingroup\$ @slepic I've updated the question. Please consider it. \$\endgroup\$ – Prateek Thapa yesterday
  • 1
    \$\begingroup\$ @KoenAIS I've updated the question. Please consider it. \$\endgroup\$ – Prateek Thapa yesterday
  • \$\begingroup\$ 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. \$\endgroup\$ – Koen AIS yesterday
0
\$\begingroup\$

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++;
    }
}
\$\endgroup\$

Your Answer

Prateek Thapa is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.