use warnings;
use strict;
sub perm_decode {
my(@perm) = @_;
my($n, $k, $b, $v, $e);
($n, $k, $b, $v) = (0, 0, 0, 0);
for $e (@perm) {
#$b == choose($n, $k - 1) or die "assertion failed";
$e or $v += $b;
$n++;
$e and $k++;
$b = $k <= 1 ?
($k < 1 ? 0 : 1) :
($b * $n / ($e ? $k - 1 : $n - $k + 1));
}
$b = $k <= 0 ? 1 : ($b * ($n - $k + 1)) / $k;
#$b == choose($n, $k) or die "assertion failed";
$n, $k, $v, $b;
}
sub perm_encode {
my($n, $k, $v) = @_;
my(@r, $bi);
while (0 < $n) {
$n--;
$bi = choose($n, $k - 1);
if ($v < $bi) {
unshift @r, 1;
$k--;
} else {
$v -= $bi;
unshift @r, 0;
}
}
@r;
}
Update. Here's how to use the above subroutine.
The perm_decode function accepts a permutation of K zeros and N-K ones as input, but the K letter word can easily be converted to such a permutation with this function. As you can see, the perm_decode function returns N, K, and C apart from the rank.
sub word_to_indicator {
my($n, $w) = @_;
my($p, $d) = 0;
reverse map {
$p += $d = chr(ord("A") + $_) eq substr($w, $p, 1) ? 1
+ : 0;
$d;
} 0 .. $n - 1;
}
if (1) {
# here, N = 5, K = 2.
my @combination = qw{AB AC AD AE BC BD BE CD CE DE};
for my $combination (@combination) {
my @indicator = word_to_indicator(5, $combination);
my($N, $K, $rank, $C) = perm_decode(@indicator);
print "$combination : @indicator : $N $K $C $rank\n";
}
}
|