Enumerate Combinations of Three Dices

The baby has been playing a color matching game with three identical dices. A dice has different colors on its faces. Every time, the three dices are thrown together, resulting in a combination of colors. The goal of the game is to find the wooden fish colored with the combination. There are 42 wooden fish provided by the game. I have some doubt that these fish does not enumerate all the color combinations. Let's set out finding out the answer.

The easy way to approach this problem without using much mental power is to have a computer solve it by brute force. The technical term of this approach is known as Monte Carlo simulation. The whole workflow is just sampling and counting and repeating. The sampling can be done with any random integer generator. The twist in the counting is how to tell the sampling results apart. This can be achieved by sorting the 3 sampled random integers.

Now the actual code in C++.

#include <cassert>
#include <cstdlib>  // For srand() and rand()
#include <ctime>    // For time()

#include <algorithm>
#include <iostream>
#include <set>


struct Triple {
  int a_, b_, c_;

 public:
  Triple() : a_(0), b_(0), c_(0) {}
  virtual ~Triple() {}
  Triple(int a, int b, int c) {
    int arr[] = {a, b, c};
    std::sort(arr, arr + 3);
    a_ = arr[0];
    b_ = arr[1];
    c_ = arr[2];
  }
  Triple(const Triple& rhs) : a_(rhs.a_), b_(rhs.b_), c_(rhs.c_) {}
  bool operator<(const Triple& rhs) const {
    if (a_ < rhs.a_) {
      return true;
    } else if (a_ == rhs.a_) {
      if (b_ < rhs.b_) {
        return true;
      } else if (b_ == rhs.b_) {
        if (c_ < rhs.c_) {
          return true;
        } else if (c_ == rhs.c_) {
          return false;
        } else {
          return false;
        }
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
  bool operator==(const Triple& rhs) const {
    if (a_ == rhs.a_ && b_ == rhs.b_ && c_ == rhs.c_) {
      return true;
    } else {
      return false;
    }
  }
  friend std::ostream& operator<<(std::ostream& os, const Triple& tp) {
    os << tp.a_ << " " << tp.b_ << " " << tp.c_;
    return os;
  }
};

Triple sampleTriple() {
  int a = (rand() % 6) + 1;
  int b = (rand() % 6) + 1;
  int c = (rand() % 6) + 1;

  return Triple(a, b, c);
}

int main(int argc, const char* argv[]) {
  int max_trial(1000);
  if (argc > 1)
    int max_trial = std::atoi(argv[1]);
  
  srand(time(0));  // Initialize random number generator.
  std::set<Triple> unique_triples;
  for (int i = 0; i < max_trial; ++i) {
    Triple tp = sampleTriple();
    unique_triples.insert(tp);
  }
  std::cout << "#Unique triples " << unique_triples.size() << " in " << max_trial
            << " trials.\n";
  for (const Triple& tp : unique_triples) {
    std::cout << tp << std::endl;
  }
  assert(unique_triples.size() == 6 * 7 * 8 / (1 * 2 * 3));
  return 0;
}

To get a feel of the result, paste the above code at here.

The Monte Carlo simulation tells us that there are 56 unique color combinations for three dices. This resolves my doubt. Indeed there are not enough wooden fish for these combinations. A natural next question is why 56.

Recall the stars and bars technique in combinatorics. To take advantage of the stars and bars, we need to rephrase the problem a bit. In the first step, let's consider a color as a bin, and a toss of a dice as an object. In other words, tossing 3 dices each of 6 colors at once is viewed as putting 3 identical objects into 6 different bins corresponding to colors. Apparently, there will be some empty bins. To simplify the problem further, in the second step, we artificially add 6 identical objects and put each into one of the 6 bins. Thus the problem can be rephrased as finding the number of ways to assign 9 identical objects into 6 unique bins with the constraint that none of the bins is empty. It can be readily solved with the above mentioned stars and bars technique. To put the 9 objects (stars) into 6 bins, we can place bars at 5 out of the 8 gaps between the stars to separate into 6 groups. And the leftmost group goes to the first bin and the rightmost group goes to the last bin. So the number of ways is $\binom{8}{5} = \binom{8}{3} =
\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1} = 56$.

Done!