Permutation-generating program

whichperm.pl

#!/usr/bin/perl

use Test::More;

# Binomial coefficients
sub choose {
  my ($n, $k) = @_;
  return 0 if $k > $n;

  my $r = 1;
  for my $d (1 .. $k) {
    $r *= $n--;
    $r /= $d;
  }
  return $r;
}

sub count_perm {
  my ($len, $sum) = @_;
  return 1 if $len == 0 && $sum == 0;
  return choose($len+$sum-1, $sum);
}

subtest "count_perm" => sub {
  is(count_perm(0, 0), 1);
  is(count_perm(0, 1), 0);
  is(count_perm(0, 2), 0);
  is(count_perm(1, 0), 1);
  is(count_perm(1, 1), 1);
  is(count_perm(1, 2), 1);
  is(count_perm(2, 0), 1);
  is(count_perm(2, 1), 2);
  is(count_perm(2, 2), 3);
  is(count_perm(3, 3), 10);
  is(count_perm(4, 2), 10);
  is(count_perm(4, 3), 20);
  is(count_perm(5, 2), 15);
};

sub perm {
  my ($N, $len, $sum) = @_;
  if ($len == 0) {
    die "len=0 but N=$N\n" unless $N == 0;
    die "len=0 but sum=$sum\n" unless $sum == 0;
    return [];
  }

  # calculate the first element
#  my $n_perms = count_perm($len, $sum);
  my $first;
  for my $f (0 .. $sum) {
    my $np = count_perm($len-1, $sum-$f);
    $first = $f, last if $N < $np;
    $N -= $np;
  }

  # recursively compute the next permutation
  my $rest = perm($N, $len - 1, $sum - $first);

  return [$first, @$rest];
}

sub perm_str { join "", @{perm(@_)} }

my @tests = qw(003 012 021 030 102 111 120 201 210 300);

subtest "perm" => sub {
  for my $i (0 .. $#tests) {
    is(perm_str($i, 3, 3), $tests[$i]);
  }
  is(perm_str(8, 5, 2), "01100");
  is(perm_str(8, 4, 2), "1100");
  is(perm_str(8, 4, 3), "0210");
};

done_testing();