「組合せ型の最小完全ハッシュ関数」の逆関数 in Ruby DouKaku?

まずは最小完全ハッシュ関数の作り方の後半部分をご覧ください。

「組み合わせ型の最小完全ハッシュ関数」とは下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)

>>> for xs in make_perm(5, 2):
	print xs, "=>", hash(xs, 5, 2)

	
[1, 1, 0, 0, 0] => 9
[1, 0, 1, 0, 0] => 8
[1, 0, 0, 1, 0] => 7
[1, 0, 0, 0, 1] => 6
[0, 1, 1, 0, 0] => 5
[0, 1, 0, 1, 0] => 4
[0, 1, 0, 0, 1] => 3
[0, 0, 1, 1, 0] => 2
[0, 0, 1, 0, 1] => 1
[0, 0, 0, 1, 1] => 0

「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)

さて、ここからが本題です。組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。

このお題はshuyoさんの提案を元に作成しました。ありがとうございました。

定義通りに実装，これで合っているはず，大丈夫かな？
comb(n,k)がn<kのときに0を返すのがミソかも．

def prod( n )
  if n == 0
    1
  else
    n * prod( n - 1 )
  end
end

def comb( n, k )
  if n < k
    0
  else
    prod( n ) / ( prod( k ) * prod( n - k ) )
  end
end

def inv_comb_hash( x, n, k )
  return [] if n == 0
  n_k_comb = comb( n - 1, k )
  if x >= n_k_comb
    [1] + inv_comb_hash( x - n_k_comb, n - 1, k - 1 )
  else
    [0] + inv_comb_hash( x, n - 1, k )
  end
end

## 以下テスト

[ [1,1],
  [2,1],
  [2,2],
  [5,2],
  [10, 5],
].each {| test |
  
  comb( test[0], test[1] ).times {| i |
    puts( ("inv_comb_hash(%3d, %3d, %3d) = %s" % \
           [ i, test[0], test[1],
             inv_comb_hash(i, test[0], test[1]).inspect, ]) )
  }
  puts
}

そうか，n=kを見れば別に末端まで再帰する必要は無いな．
おれはまだまだ修行が足りなかったようだ．
下に自分のコードを書き直してみた，エンバグしてなきゃいいけど．

see:

def fact( n )
  if n == 0
    1
  else
    n * fact( n - 1 )
  end
end

def comb( n, k )
  fact( n ) / ( fact( k ) * fact( n - k ) )
end

def inv_comb_hash( x, n, k )
  if n == 0
    return []
  elsif n == k
    return [1] * n
  end
  nCk = comb( n - 1, k )
  if x >= nCk
    [1] + inv_comb_hash( x - nCk, n - 1, k - 1 )
  else
    [0] + inv_comb_hash( x, n - 1, k )
  end
end

DouKaku?

「組合せ型の最小完全ハッシュ関数」の逆関数

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq