1. Problem
Given N dices and each dice with S sides compute how many combinations there are when the sum of N dices is equal to K.
An example is that given the conventional dice with 6 sides, each sides with value 1, 2, ..., 6. If have 6 dices,
compute SUM K = 37, the answer is 0 - impossible.
compute SUM K = 36, the answer is 1 - all of them are on side 6.
compute SUM K = 35, the answer is 6 - 5 of them are on side 6 and 1 on side 5.
......
compute SUM K = 6, the answer is 1 - all of them are on side 1.
compute SUM K = 5, the answer is 0 - impossible
Let's say:
Si denotes the value of dice side. A dice has S sides.
Si presents the value i. (i = 1, 2, 3, ..., S).
N denotes how many dices are given.
K denotes SUM of N dices after rolling.
Then the number of combinations can be represented as f(S, N, K)
2. Solutions formulation
There are 3 ways to tackle this issue as I can think of. I will go through all of them. One of them is dynamic programming, which I will concentrate on.
Solution space:
This is the first formation that I can think of as I have worked on the variable/equation related solvers in the last a few years.
Let Xi denotes the i-th dice's vale. One equation can be formulated as
X1+ X2 + ......+ XN = K;
where Xi is bounded by [1, S].
The solution space will be N variables with N constraints but only 1 equation. The variable outnumbers the equation, then we may have multi-solutions. Given a SUM K, then number of combination is equal to the number of solution of this equation under the constraints.
Polynomial multiplication:
Represent the dice with S sides as:
a1*x + a2*x^2 + a3*x^3 + ...... + aS*x^S
And because the dice has the even opportunity to roll to any side (1, 2, 3, ..., S), then a1, a2, a3, ..., aS will have the same value and is equal to 1.
a1 = a2 = a3 = ...... = aS = 1
Hence the polynomial can be simplified as:
x + x^2 + x^3 + ......+ x^S
With the N dices:
(x + x^2 + x^3 + ...... + x^S)^N
So after the multiplication of above polynomial, then we will have something like
b1*x^N + b2*x^(N+1) + ...... + b(S*N)*x^(S*N)
It is clear that,
b1 = b(S*N) = 1,
b2 = b(S*N-1) = N,
......
Given a K bounded in [N, S*N], the number of combination of SUM K will be bK.
Dynamic programming:
The key issue for dynamic programming is to work out the sub-problem[1][2]. Let me illustrate out the sub-problem of f(S, N, K).
Given the fact one dice has S sides. Assume we know the side of one dice, then what can we re-define the problem? If the side value is Si, then we have N-1 dices left, which will have to has the SUM of K-Si.
Si = 1, then sub problem is f(S, N-1, K-1);
Si = 2, then sub problem is f(S, N-1, K-2);
.......
Si = S, then sub problem is f(S, N-1, K-S);
Then the problem can be written as:
f(S, N, K) = sigma(f(S, N-1, K-Si)) ,
where Si bounded [1, S]
3. Solution of Dynamic programming
As usual dynamic programming is normally written as a recursive function. Here comes the program under Microsoft Visual C++ 2010 Express.
*********************************************************************************
#include "stdafx.h"
#include <map>
#include <utility>
typedef std::pair<size_t, size_t> DiceKey;
typedef std::map<DiceKey, size_t> DiceCacheMap;
size_t SumOfDiceAlg(long s, long n, long k, DiceCacheMap &dcm)
{
if (k < n || k > (n*s)) {
// no solution found in this case
return 0;
}
if (n == 1 && k > 0 && k <= s) {
// found a solution here
return 1;
}
const DiceKey key = std::make_pair(n, k);
if (dcm.find(key) != dcm.end()) {
return dcm[key];
}
// this loop is the sub-problem illustration
// f(S, N, K) = sigma(f(S, N-1, K-Si))
size_t count = 0;
for (long j = 1; j <= s; ++j) {
count += SumOfDiceAlg(s, n - 1, k - j, dcm);
}
dcm.insert(std::make_pair(key, count));
return count;
}
size_t SumOfDice(long s, long n, long k)
{
DiceCacheMap dcm;
size_t count = SumOfDiceAlg(s, n, k, dcm);
return count;
}
int _tmain(int argc, _TCHAR* argv[])
{
// S=6, N=6 and SUM=23
SumOfDice(6, 6, 23);
return 0;
}
*********************************************************************************
It is worth pointing out that the caching technique is used in this short program to speed up the performance, because there is no need to go through the same sub-problem twice by the same load of computation.
An example of the same sub-problem:
6th dice value 5th dice value sub-problem
3 4 f(6, 4, 16) // 4 dice left, sum updated as 16 (23 - 3 - 4)
5 2 f(6, 4, 16) // 4 dice left, sum updated as 16 (23 - 5 - 2)
Then the same sub-problem f(6, 4, 16) is no need to compute again.
Bibliography:
[1] Richard Bellman, "Dynamic Programming", 2003 print
[2] http://en.wikipedia.org/wiki/Dynamic_programming
No comments:
Post a Comment