「組合せ型の最小完全ハッシュ関数」の逆関数
Posted feedbacks - R
kkobayashi
#1658()
[
R
]
統計解析パッケージであるRの出番ですね（？）
例と出力を合せるために少し変な書き方をしています。
> for(i in 9:0){
+ cat(i, "=>", rev.hash(i, 5, 2), "\n")
+ }
9 => 1 1 0 0 0
8 => 1 0 1 0 0
7 => 1 0 0 1 0
6 => 1 0 0 0 1
5 => 0 1 1 0 0
4 => 0 1 0 1 0
3 => 0 1 0 0 1
2 => 0 0 1 1 0
1 => 0 0 1 0 1
0 => 0 0 0 1 1
1 2 3 4 5 | rev.hash <- function(x, n, m){
data <- rep(1, n)
data[combn(n, n-m)[,x+1]] <- 0
return(data)
}
|
shuyo
#3392()
Rating0/0=0.00
「組み合わせ型の最小完全ハッシュ関数」とは 下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)
「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、 ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)
さて、ここからが本題です。 組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。 この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。
このお題はshuyoさんの提案を元に作成しました。ありがとうございました。
[ reply ]