タグ

algorithmとhashに関するamachangのブックマーク (2)

  • 最小完全ハッシュ関数の作り方 を JavaScript で - てっく煮ブログ

    JavaScriptActionScript/Flex ネタが続いているので、たまには JavaScript ネタを。はてブ経由で知った 最小完全ハッシュ関数の作り方 が面白そうだったのだけど、「最小完全ハッシュ関数」が何か分からないまま読み進めたら、やっぱり話が分からなくなってしまった。分からないまま JavaScript に移植。 /* 順列型の最小完全ハッシュ関数 */ function ChangeNumber(arr) { var work = arr.concat(); var hash = 0; // 階乗値テーブル作成 var FACTOR = [1]; for(var i=0; i { FACTOR.unshift(FACTOR[0] * (i+1)); } for(var i=0; i { hash += work[i] * FACTOR[i]; for (j=i+1;

    amachang
    amachang 2007/05/07
    JavaScript で順列のハッシュ関数を実装。「アルゴリズムの挙動は頭で考えるよりも、実際に手を動かしたほうが理解しやすい。」名言!
  • 最小完全ハッシュ関数の作り方

    ■順列型の最小完全ハッシュ関数 0から4までの5個の数字が下のように並んでいる場合を例にして説明します。 5個の数字の並べ方は5!通りありますので5!(=120)通りの並べ方の総てに対して0から119までの数値を一意に割り付けることが目的となります。 34102 ここでは左側から順に数字を見ていくことにします。最初の数字は3で残りの数字の個数は4個ですね。 この残れさた数字の個数分の総順列数は4!ですが、この数量を基数と言います。 つまり左端の数字が何であるかを完全に識別する為に最低限必要な基となる重みのことです。 従って先ず最初の数字3に基数である4!を掛け算してはじき出します。 [3]4102 → 3*4! 次に左から2番目の数字ですが、ここから先はとても注意が必要です。 2番目の数字は4で残りの数字の個数は3個です。残りの数字の個数が3個なので基数は3!になります。つまり基数が変化

    amachang
    amachang 2007/05/06
    順列型および組合せ型の最小完全ハッシュの求めかた。考え方とその実装を詳しく解説。これはとても面白い。
  • 1