Pideonholes revisited.

[BrowserUk]

In Combinatorics problem. (Updated with more info.) I asked how to efficiently distribute N cards amongst M pigeon holes where each hole must contain at least one card.

I've now realised that for some variations of the problem I dealing with, I need to allow for the situation where the first or last pigeon hole, or both, can be zero.

I thought this would be a simple tweak to the answers I already received; but once again I've come unstuck for an efficient solution. Is there one?

[VinsWorldcom]

Just a quick thought, could you use a previous scripting answer from the other thread and run it for M=M, M=M-1 (first or last hole = 0) and M=M-2 (first and last hole = 0), and then just stitch all the answers together?

[BrowserUk]

Yes. That does it perfectly. (Simple, when someone shows you how :)

#! perl -slw
use strict;

sub arrange {
    my( $code, $used, $remaining, $total, $prefix ) = @_;

    return $code->( @$prefix, $remaining ) if ++$used == $total;

    arrange( $code, $used, $remaining - $_, $total, [ @$prefix, $_ ] )
+ for 1 .. $remaining - ( $total - $used );
}

our $cards        //= 5;
our $holes        //= 3;

arrange sub {
    print "[ @_ ]";
}, 0, $cards, $holes, [];

arrange sub {
    print "[ 0 @_ ]";
    print "[ @_ 0 ]";
}, 0, $cards, $holes -1, [];

arrange sub {
    print "[ 0 @_ 0 ]";
}, 0, $cards, $holes -2, [];

__END__
C:\test>1149981-gf -cards=5 -holes=3
[ 1 1 3 ]
[ 1 2 2 ]
[ 1 3 1 ]
[ 2 1 2 ]
[ 2 2 1 ]
[ 3 1 1 ]
[ 0 1 4 ]
[ 1 4 0 ]
[ 0 2 3 ]
[ 2 3 0 ]
[ 0 3 2 ]
[ 3 2 0 ]
[ 0 4 1 ]
[ 4 1 0 ]
[ 0 5 0 ]

div class=

[hdb]

You really should only work on the distribution of cards on top of the minimum for each hole and add that minimum later.