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

[download]

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
[reply]
      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

[reply]
        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;
}

        [download]

        Cheers - L~R

[reply]
[d/l]

In Section Seekers of Perl Wisdom