unordered sets of N elements

[japhy]

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;

[Limbic~Region]

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).

[dragonchild]

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.

[japhy]

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.

[dragonchild]

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. :-)

[japhy]

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.

[dragonchild]

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.

[kvale]

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)

[hv]

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);

Presenting the strings reversed instead allows a slightly cleaner solution with a (rare) useful use of 'cut' - just change the pattern to:

  ( (?>$die*) (.))

.. and the cut takes up the role of the negative lookahead in ensuring that our incremented digit cannot itself be a match for $die.

Hugo