Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

unordered sets of N elements

by japhy (Canon)
on Jul 13, 2004 at 13:16 UTC ( #373967=perlquestion: print w/ replies, xml ) Need Help??
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

Comment on unordered sets of N elements
Select or Download Code
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);

    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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://373967]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (8)
As of 2014-12-26 20:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (176 votes), past polls