「組合せ型の最小完全ハッシュ関数」の逆関数
Posted feedbacks - Perl
オーソドックスな実装。nCkの定義は、 n C k = k C n にあわせました。 Dan the Perl Monger
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #!/usr/local/bin/perl
use strict;
use warnings;
sub fact{ $_[0] <= 1 ? 1 : $_[0] * fact($_[0]-1) };
sub nCk {
my ($n, $k) = ($_[0] > $_[1]) ? @_ : reverse @_;
fact($n) / fact($k) / fact($n - $k)
}
sub invhash {
my ( $x, $n, $k ) = @_;
return () if $n == 0;
return (1) x $n if $n == $k;
my $c = nCk( $n - 1, $k );
$x >= $c ? (1, invhash( $x - $c, $n - 1, $k - 1 ))
: (0, invhash( $x, $n - 1, $k ));
}
print $_, " => [", join(", ", invhash($_, 5, 2)), "]\n" for (0..9);
|
shuyo
#3392()
Rating0/0=0.00
「組み合わせ型の最小完全ハッシュ関数」とは 下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)
「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、 ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)
さて、ここからが本題です。 組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。 この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。
このお題はshuyoさんの提案を元に作成しました。ありがとうございました。
[ reply ]