Re: Combinatorics problem.

[GrandFather]

Maybe not over efficient, at least on memory, but:

#!/usr/bin/perl
use strict;
use warnings;

my $cards        = 5;
my $holes        = 3;
my @arrangements = arrange(0, $cards, $holes);

print "@$_\n" for @arrangements;


sub arrange {
    my ($usedHoles, $remainingCount, $totalHoles) = @_;
    my @arrangements;

    return [$remainingCount] if ++$usedHoles == $totalHoles;

    for my $thisCount (1 .. $remainingCount - ($totalHoles - $usedHole
+s)) {
        my @subArrangements =
            arrange($usedHoles, $remainingCount - $thisCount, $totalHo
+les);

        push @arrangements, map {[$thisCount, @$_]} @subArrangements;
    }

    return @arrangements;
}

Prints:

1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1

Update: avoiding most of the memory usage:

#!/usr/bin/perl
use strict;
use warnings;

my $cards        = 5;
my $holes        = 3;

arrange(0, $cards, $holes, '');


sub arrange {
    my ($usedHoles, $remainingCount, $totalHoles, $prefix) = @_;

    if (++$usedHoles == $totalHoles) {
        print "$prefix $remainingCount\n";
        return;
    }

    for my $thisCount (1 .. $remainingCount - ($totalHoles - $usedHole
+s)) {
        arrange($usedHoles, $remainingCount - $thisCount, $totalHoles,
+ "$prefix $thisCount");
    }
}

[BrowserUk]

Update: avoiding most of the memory usage:

That's perfect. Thankyou.

It generates the 462 of my bastard testcase instantly:

C:\test>1149981-gf -cards=12 -holes=7 | wc -l
    462

I'll probably try and turn it into an iterator once my brain's in gear; but the algorithm is spot on. Thanks again.