japhy has asked for the wisdom of the Perl Monks concerning the following question:

I've looked at permutations and combinations, and have decided they're not what I'm looking for. I have a game at home called Six Cubes. It's a dice game -- you roll six dice, and if specific combinations come up, you can store them away for points, and decide to roll the remaining dice or stop. The dice are your standard d6 (that's a gaming term).

I'm trying to calculate the number of rolls possible. Everything from "1 1 1 1 1 1" to "6 6 6 6 6 6". However, the roll "1 1 1 1 1 2" is no different from "1 1 1 2 1 1". I'm trying to determine the mathematical approach to calculating the number of rolls possible. I can produce them (there are 462), but I can't figure out a generic mathematical formula to get that number.

From a regex standpoint, it's /^(?=.{6}\$)1*2*3*4*5*6*/. (This is extraneous, but it defines the strings that match. "111112" is valid, "121111" is not,, because it's "identical".)

Here's my Perl code. It looks eerily familiar, like I've seen this somewhere before, but I don't know where offhand:

```sub unordered_sets {
my (\$in, \$out, \$left, \$idx, \$curr) = @_;
push @\$out, [@\$curr] and return if \$left == 0;
\$idx ||= 0;
for (\$idx .. \$#\$in) {
push @\$curr, \$in->[\$_];
unordered_sets(\$in, \$out, \$left-1, \$_, \$curr);
pop @\$curr;
}
}

my @sets;
unordered_sets [1..6], \@sets, 6;
_____________________________________________________
Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart

Replies are listed 'Best First'.
Re: unordered sets of N elements
by Limbic~Region (Chancellor) on Jul 13, 2004 at 13:36 UTC
japhy,
Here is the mathematical formula with a little help from google.
```(N+5) (N+4) (N+3) (N+2) (N+1) / 120
If I were solving the problem using code and I couldn't figure out how to use one of those nifty CPAN modules, I would do it the inefficient way (sort, join, use a hash).

Cheers - L~R

Or, to take it to any number of sides:
``` k-1
-----
| |  (N+i)
i=1
-------------
(k-1)!

Where N is the number of dice and k is the number of sides. The Pi is like Sigma, but for multiplication instead of addition.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested

Wow. That's amazing. Thanks for finding that link for me. I hadn't used "dice" in my googling, and never found anything remotely close to what I needed.
_____________________________________________________
Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
Re: unordered sets of N elements
by dragonchild (Archbishop) on Jul 13, 2004 at 13:42 UTC
You are looking for combinations. Just with additional constraints. Look at a simpler example - 2 dice. Your rules says that 1-3 and 3-1 are the same. So, we take the first number in the first die and look at the possibilities in the second - 6. Then we take the second number in the first die, leaving us 5 possibilities in the second die. (The sixth, 2-1, is disallowed). Following the pattern leaves us 6+5+4+3+2+1 = 21 possibilities.

Extending to three dice, we have the following - set to 1-1 and we have 6 possibilities. 1-2 and we have 5, etc. So, with the first die as 1, we have the above 21 possibilities. Setting the first die to 2 and we have 5 possibilities for the second and 4 for the third - leaving us 15 total possibilities. So, the total ends up being 21 + 15 + 10 + 6 + 3 + 1 = 56, which is borne out by your code.

You can extend the pattern upwards. The actual formula involves a bunch of Sigmas.

```d = 6, n = 2 ==> S(i=1->d)(i)
d = 6, n = 3 ==> S(i=1->d)(S(j=1->i)(j)

The inductive rule is:
F(2) ==> S(i=1->d)(i)
F(n) ==> S(i=1->d)(F(n-1))

I'm sure there's a straight formula, but my brain hurts. :-)

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested

Yes, I'd worked on this last night by hand, starting with smaller data sets. I saw the triangular pattern evolving, but wasn't sure where to go with it. Your inductive formula is a big help.
_____________________________________________________
Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
If you want to solve it recursively, the induction is good. However, I'd use L~R's googled formula with my mod for different number of sides.

Note - none of the formulas help if you have 2d6+2d8 with the same constraint across all four dice.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested

Re: unordered sets of N elements
by kvale (Monsignor) on Jul 13, 2004 at 15:32 UTC
Answering the next logical question, you can calculate the probability of particular dice rolls using the multinomial distribution. For x1 1's, ... x6 6's, where  x1+x2+x3+x4+x5+x6 = 6, the probability is
```Prob( x1, x2, x3, x4, x5, x6) =
(6! / (x1! * x2! * x3! * x4! * x5! * x6!)) * 6**(-6)

-Mark

Re: unordered sets of N elements
by hv (Parson) on Jul 13, 2004 at 20:55 UTC

If you want an iterator (rather than a recursive function that returns all relevant combinations), that is easy too: it's just like counting in base n, except that when you overflow you reset the overflowing digit not to zero but to the same (new) value as the preceding digit:

```  sub next_iter {
my(\$count, \$die, \$current) = @_;
return '1' x \$count unless \$current;
\$current =~ s{
(?!\$die) ((.) \$die*) \$
}{
my \$d = \$2 + 1;
\$d x length \$2
}ex or return undef;
return \$current;
}
...
my \$cur;
print \$cur while \$cur = next_iter(3, 6, \$cur);
```  ( (?>\$die*) (.))