Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: unordered sets of N elements

by dragonchild (Archbishop)
on Jul 13, 2004 at 13:42 UTC ( [id://373979]=note: print w/replies, xml ) Need Help??


in reply to unordered sets of N elements

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

Replies are listed 'Best First'.
Re^2: unordered sets of N elements
by japhy (Canon) on Jul 13, 2004 at 13:47 UTC
    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

        dragonchild,
        That may be where using one of those nifty CPAN modules and sorting/joining/hashing comes into play.
        #!/usr/bin/perl use strict; use warnings; use Algorithm::Loops 'NestedLoops'; my (@combo, %seen); my %roll = ( 'type1' => { 'sides' => 6, 'count' => 2 }, 'type2' => { 'sides' => 8, 'count' => 2 }, ); my $die = 4; my $iter = NestedLoops( [ map { ( [1..$_->{sides}] ) x $_->{count} } values %roll ], { OnlyWhen => \&ok } ); print "@combo\n" while ( @combo = $iter->() ); sub ok { my $key = join '' , sort @_; return undef if exists $seen{$key} || length $key != $die; $seen{$key} = undef; return 1; }

        Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://373979]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others romping around the Monastery: (3)
As of 2024-03-29 07:16 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found