I'm trying to model Yahtzee (a dice game).
As a first step, I'm trying to enumerate all possible combinations of 5 dice being rolled simultaneously. I only want unique combinations (e.g. 5,5,5,4,4 is the same as 5,5,4,5,4 and so on). Is there an easy way to do this in Python, C++, or Mathematica?
You can use itertools.combinations_with_replacement() in Python:
from itertools import combinations_with_replacement
options = list(range(1, 7))
print(list(combinations_with_replacement(options, 5)))
The solution using itertools.combinations_with_replacement is almost certainly the best (in Python, anyway), since it is both fast and easy to use. But the recursive algorithm to solve this problem is so simple and pretty that it would be a shame not to show it.
To ensure that the combination of rolls be unique, we simply need to generate it in sorted order. Every combination of rolls has a single unique sort, and we can generate every sorted combination by always appending a new value which is at least as large as the previous value in the combination.
Translating that to Python:
def rolls(n, k=6):
'''Generate distinct rolls of n k-sided dice'''
if n:
for i in range(k, 0, -1):
for roll in rolls(n-1, i):
yield roll + [i]
else:
yield []
That generates the combinations in reverse colex order, although it can easily be modified to produce colex order, by changing the range to range(1, k+1).
This will list all 252 permutations in Mathematica.
Union[Sort /@ Tuples[Range[6], {5}]]