Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Combinatorics problem.

by Anonymous Monk
on Dec 11, 2015 at 08:36 UTC ( [id://1149991]=note: print w/replies, xml ) Need Help??


in reply to Combinatorics problem. (Updated with more info.)

I think its something like that:
$cards -= $holes; # one card per hole is required, # so let's disregard those right away my $r = $cards; my $n = $cards + $holes - 1; my $result = factorial($n) / ( factorial($r) * factorial($n - $r) ); sub factorial { use List::Util 'reduce'; return 1 if $_[0] <= 0; return reduce { $a * $b } 1 .. $_[0]; }
If that's correct, i'll have more time for explanations later :)

Replies are listed 'Best First'.
Re^2: Combinatorics problem.
by Anonymous Monk on Dec 11, 2015 at 10:39 UTC
    hacky solution :)
    ## usage example: ## program.pl -cards 5 -holes 3 use strict; use warnings; use feature 'say'; use Getopt::Long; use Algorithm::Combinatorics 'combinations'; main(); exit 0; sub main { GetOptions( 'cards=i' => \my $cards, 'holes=i' => \my $holes ); die unless $cards and $holes; # TODO: more robust error checks # for now let's just assume that the user is sane :) $cards -= $holes; my $tot = $cards + $holes - 1; my $combos = combinations( [ 0 .. $tot - 1 ], $cards ); while ( my $combo = $combos->next() ) { my $hack = '0' x $tot; # total hack! :) for my $c (@$combo) { substr( $hack, $c, 1, '1' ); } say join ', ', map length() + 1, split /0/, $hack, -1; } }
    example:
    $ perl buk.pl -c 12 -h 7 | wc -l 462
      okay, less of a hack :)
      ## usage example: ## program.pl -cards 5 -holes 3 use strict; use warnings; use feature 'say'; use Getopt::Long; use Algorithm::Combinatorics 'combinations'; main(); exit 0; sub main { GetOptions( 'cards=i' => \my $cards, 'holes=i' => \my $holes ); die "Usage: $0 -c CARDS -h HOLES\n" if !defined($cards) || !defined($holes) || $cards <= 0 || $holes <= 0 || $cards < $holes; $cards -= $holes; my $tot = $cards + $holes - 1; my $combos = combinations( [ 0 .. $tot - 1 ], $cards ); while ( my $combo = $combos->next() ) { my @result = (1) x $holes; for my $i ( 0 .. @$combo - 1 ) { $result[ $combo->[$i] - $i ] += 1; } say join ', ', @result; } }
Re^2: Combinatorics problem.
by Discipulus (Canon) on Dec 11, 2015 at 21:11 UTC
    i'll be glad to read your explanation of using binomial coefficients..

    was my first intuition but my math fu is so low. Thanks anyway for the clever solution.

    L*
    There are no rules, there are no thumbs..
    Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
      So we're trying to distribute 5 cards over 3 holes. Here're the holes:
      |_|_|_|
      Let's put the cards there. Well, they won't fit, because the '_' (underscore) occupies the whole cell, rather than just the bottom of it. Let's get rid of underscores. They're just for visials anyway.
      | | | |
      Now it fits. One way to do it:
      1 1 |1|1|1|
      or maybe like this:
      1 1 |1|1|1|
      First, the bottom row of ones is always the same. We don't actually need it to count combination. Lets just remove it (like in tetris). The number of ways to distribute 5 cards over 3 holes with BUK's constraint is the same as the number of ways to distribute 2 cards over 3 holes without this constraint.
      1) |1|1| | 2) | |1|1| 1 3) | | |1| 4) and so on
      That actually looks like a datastructure we can work with. The problem is it's two dimensional. Which is kind of a pain. But! we can flatten it. Like so:
      1) | |1|1| 2) |1|1| | 3) |11| | | 4) | |11| | 5) and so on
      Now there are two more things. The spaces in empty holes are not necessary. Also, the two '|' (pipes) at the left and right edges of our strings are not necessary either. That's also just visuals. Let's remove that stuff.
      1) | | |11| => ||11 => 0 0 2 2) |1|1| | => 1|1| => 1 1 0 3) | |11| | => |11| => 0 2 0 4) etc
      For no particular reason I used '0' instead of '|' in hacky solution :) (hm, I think that's because it reminded me of a recent thread). Like that:
      1) 0011 => 0 0 2 2) 1010 => 1 1 0 3) 0110 => 0 2 0
      Now we just want to count all combinations of such strings. The length of a string is $cards (which is the number of ones) + $holes - 1 (which is the number of zeros). That's our $n. And $r is obviously the number of cards. Think of it this way:
      0000 - start with string of all zeros .00. - take some zeroes that way 1001 - and replace with ones 0..0 - take some zeroes that way 0110 - and replaces with ones 00.. - then that way 0011 - you got the idea
      Hopefully now its clear that the number of ways we can produce such strings is n! / (r!(n-r)!), just like in a textbook.

      And my hacky solution literally builds these strings and counts the length of sequences of ones :) Which is a bit of a nonsense, and GrandFather's method is a lot better, but hey! it works ;)

Re^2: Combinatorics problem.
by Anonymous Monk on Dec 11, 2015 at 08:55 UTC
    Oops, didn't notice you wanted to generate the combinations themselves too. I'll do it a bit later.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2024-03-28 23:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found