Calculate the number of ways to roll a certain num

问题:

I'm a high school Computer Science student, and today I was given a problem to:

Program Description: There is a belief among dice players that in throwing three dice a ten is easier to get than a nine. Can you write a program that proves or disproves this belief?

Have the computer compute all the possible ways three dice can be thrown: 1 + 1 + 1, 1 + 1 + 2, 1 + 1 + 3, etc. Add up each of these possibilities and see how many give nine as the result and how many give ten. If more give ten, then the belief is proven.

I quickly worked out a brute force solution, as such

int sum,tens,nines;
    tens=nines=0;

    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                sum=i+j+k;
                //Ternary operators are fun!
                tens+=((sum==10)?1:0);
                nines+=((sum==9)?1:0);
            }
        }

    }
    System.out.println("There are "+tens+" ways to roll a 10");
    System.out.println("There are "+nines+" ways to roll a 9");

Which works just fine, and a brute force solution is what the teacher wanted us to do. However, it doesn't scale, and I am trying to find a way to make an algorithm that can calculate the number of ways to roll n dice to get a specific number. Therefore, I started generating the number of ways to get each sum with n dice. With 1 die, there is obviously 1 solution for each. I then calculated, through brute force, the combinations with 2 and 3 dice. These are for two:

There are 1 ways to roll a 2
There are 2 ways to roll a 3
There are 3 ways to roll a 4
There are 4 ways to roll a 5
There are 5 ways to roll a 6
There are 6 ways to roll a 7
There are 5 ways to roll a 8
There are 4 ways to roll a 9
There are 3 ways to roll a 10
There are 2 ways to roll a 11
There are 1 ways to roll a 12

Which looks straightforward enough; it can be calculated with a simple linear absolute value function. But then things start getting trickier. With 3:

There are 1 ways to roll a 3
There are 3 ways to roll a 4
There are 6 ways to roll a 5
There are 10 ways to roll a 6
There are 15 ways to roll a 7
There are 21 ways to roll a 8
There are 25 ways to roll a 9
There are 27 ways to roll a 10
There are 27 ways to roll a 11
There are 25 ways to roll a 12
There are 21 ways to roll a 13
There are 15 ways to roll a 14
There are 10 ways to roll a 15
There are 6 ways to roll a 16
There are 3 ways to roll a 17
There are 1 ways to roll a 18

So I look at that, and I think: Cool, Triangular numbers! However, then I notice those pesky 25s and 27s. So it's obviously not triangular numbers, but still some polynomial expansion, since it's symmetric.
So I take to Google, and I come across this page that goes into some detail about how to do this with math. It is fairly easy(albeit long) to find this using repeated derivatives or expansion, but it would be much harder to program that for me. I didn't quite understand the second and third answers, since I have never encountered that notation or those concepts in my math studies before. Could someone please explain how I could write a program to do this, or explain the solutions given on that page, for my own understanding of combinatorics?

EDIT: I'm looking for a mathematical way to solve this, that gives an exact theoretical number, not by simulating dice

回答1:

The solution using the generating-function method with N(d, s) is probably the easiest to program. You can use recursion to model the problem nicely:

public int numPossibilities(int numDice, int sum) {
    if (numDice == sum)
        return 1;
    else if (numDice == 0 || sum < numDice)
        return 0;
    else
        return numPossibilities(numDice, sum - 1) +
               numPossibilities(numDice - 1, sum - 1) -
               numPossibilities(numDice - 1, sum - 7);
}

At first glance this seems like a fairly straightforward and efficient solution. However you will notice that many calculations of the same values of numDice and sum may be repeated and recalculated over and over, making this solution probably even less efficient than your original brute-force method. For example, in calculating all the counts for 3 dice, my program ran the numPossibilities function a total of 15106 times, as opposed to your loop which only takes 6^3 = 216 executions.

To make this solution viable, you need to add one more technique - memoization (caching) of previously calculated results. Using a HashMap object, for example, you can store combinations that have already been calculated and refer to those first before running the recursion. When I implemented a cache, the numPossibilities function only runs 151 times total to calculate the results for 3 dice.

The efficiency improvement grows larger as you increase the number of dice (results are based on simulation with my own implemented solution):

# Dice | Brute Force Loop Count | Generating-Function Exec Count
3      | 216 (6^3)              | 151
4      | 1296 (6^4)             | 261
5      | 7776 (6^5)             | 401
6      | 46656 (6^6)            | 571
7      | 279936 (6^7)           | 771
...
20     | 3656158440062976       | 6101

回答2:

You don't need to brute force since your first roll determines what values can be used in the second roll, and both first and second roll determine the third roll. Let's take the tens example, suppose you roll a 6, so 10-6=4 meaning you still need 4. For the second roll you need at least 3, because your third roll should at least count for 1. So the second roll goes from 1 to 3. Suppose your second roll is 2, you have 10-6-2=2, meaning your third roll IS a 2, there is no other way.

Pseudo code for tens:

tens = 0

for i = [1..6] // first roll can freely go from 1 to 6
   from_j = max(1, 10 - i - 6) // We have the first roll, best case is we roll a 6 in the third roll
   top_j = min(6, 10 - i - 1) // we need to sum 10, minus i, minus at least 1 for the third roll
   for j = [from_j..to_j]
      tens++

Note that each loop adds 1, so at the end you know this code loops exactly 27 times.

Here is the Ruby code for all 18 values (sorry it's not Java, but it can be easily followed). Note the min and max, that determine what values can have each of the dice rolls.

counts = [0] * 18

1.upto(18) do |n|
  from_i = [1, n - 6 - 6].max # best case is we roll 6 in 2nd and 3rd roll
  top_i = [6, n - 1 -1].min # at least 1 for 2nd and 3rd roll
  from_i.upto(top_i) do |i|
    from_j = [1, n - i - 6].max # again we have the 2nd roll defined, best case for 3rd roll is 6
    top_j = [6, n - i -1].min # at least 1 for 3rd roll
    from_j.upto(top_j) do
      # no need to calculate k since it's already defined being n - first roll - second roll
      counts[n-1] += 1
    end
  end
end

print counts

For a mathematical approach, take a look at https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t

回答3:

Mathematical description is just a 'trick' to make same counting. It uses polynomial to express dice, 1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x means that each value 1-6 is counted once, and it uses polynomial multiplication P_1*P_2 for a counting of different combinations. That is done since coefficient at some exponent (k) is calculated by summing all coefficient in P_1 and P_2 which exponent sum to k.

E.g. for two dices we have:

(1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x) * (x^6 + x^5 + x^4 + x^3 + x^2 + x) = 
(1*1)*x^12 + (1*1 + 1*1)*x^11 + (1*1 + 1*1 + 1*1)*x^11 + ... + (1*1 + 1*1)*x^3 + (1*1)*x^2

Calculation by this method has same complexity as 'counting' one.

Since function (x^6 + x^5 + x^4 + x^3 + x^2 + x)^n has simpler expression (x(x-1)^6/(x-1))^n, it is possible to use derivation approach. (x(x-1)^6/(x-1))^n is a polynomial, and we are looking for coefficient at x^s (a_s). Free coefficient (at x^0) of s'th derivation is s! * a_k. So, s'th derivation in 0 is s! * a_k.

So, we have to derive this function s times. It can be done using derivation rules, but I think that it will have even worse complexity than counting approach since each derivation produces 'more complex' function. Here are first three derivations from Wolfram Alpha: first, second and third.

In general, I prefer counting solution, and mellamokb gave nice approach and explanation.

回答4:

Check out Monte Carlo Methods they usually scale linearly with inputsize. In this case the example is easy, we assume that since once throw of the dice doesn't affect the other instead of counting combinations we can simply count the sum of the faces of dices thrown randomly (many times enough).

   public class MonteCarloDice {

    private Map<Integer, Integer> histogram;
    private Random rnd;
    private int nDice;
    private int n;

    public MonteCarloDice(int nDice, int simulations) {
        this.nDice = nDice;
        this.n = simulations;
        this.rnd = new Random();
        this.histogram = new HashMap<>(1000);
        start();
    }

    private void start() {
        for (int simulation = 0; simulation < n; simulation++) {
            int sum = 0;
            for (int i = 0; i < nDice; i++) {
                sum += rnd.nextInt(6) + 1;
            }
            if (histogram.get(sum) == null)
                histogram.put(sum, 0);
            histogram.put(sum, histogram.get(sum) + 1);
        }
        System.out.println(histogram);
    }


    public static void main(String[] args) {
        new MonteCarloDice(3, 100000);
        new MonteCarloDice(10, 1000000);
    }

}

The error decreases with number of simulations but at the cost of cputime but the above values were pretty fast.

3 dice

{3=498, 4=1392, 5=2702, 6=4549, 7=7041, 8=9844, 9=11583, 10=12310, 11=12469, 12=11594, 13=9697, 14=6999, 15=4677, 17=1395, 16=2790, 18=460}

10 dice

{13=3, 14=13, 15=40, 17=192, 16=81, 19=769, 18=396, 21=2453, 20=1426, 23=6331, 22=4068, 25=13673, 24=9564, 27=25136, 26=19044, 29=40683, 28=32686, 31=56406, 30=48458, 34=71215, 35=72174, 32=62624, 33=68027, 38=63230, 39=56008, 36=71738, 37=68577, 42=32636, 43=25318, 40=48676, 41=40362, 46=9627, 47=6329, 44=19086, 45=13701, 51=772, 50=1383, 49=2416, 48=3996, 55=31, 54=86, 53=150, 52=406, 59=1, 57=2, 56=7}