「組合せ型の最小完全ハッシュ関数」の逆関数
Posted feedbacks - diff
バグではないのですが、std::fill()というアルゴリズムがあることに気づいたので、リファクタリング。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | --- main.orig Thu Aug 2 14:52:35 2007
+++ main.cpp Thu Aug 2 14:56:58 2007
@@ -13,10 +13,7 @@
std::vector<int> v(n, 1);
- for (size_t i = 0; i < n - m; ++i)
- {
- v[i] = 0;
- }
+ std::fill(v.begin(), v.begin() + (n - m), 0);
for (size_t i = 0; i < x; ++i)
{
|
と思ったらstd::fill_nがあるので、こっちの方が短いな・・・（度々すみません）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | --- main.orig Thu Aug 2 14:52:35 2007
+++ main.cpp Thu Aug 2 15:07:37 2007
@@ -13,10 +13,7 @@
std::vector<int> v(n, 1);
- for (size_t i = 0; i < n - m; ++i)
- {
- v[i] = 0;
- }
+ std::fill_n(v.begin(), n - m, 0);
for (size_t i = 0; i < x; ++i)
{
|
shuyo
#3392()
Rating0/0=0.00
「組み合わせ型の最小完全ハッシュ関数」とは 下のような「n個の値のうちm個が1で残りが0であるようなデータ」と整数とを対応づける関数です。下の例ではn=5でm=2になっています。 (「0以上n未満の整数から重複しないm個を選んだ組み合わせ」もデータとしては同じです)
「ハッシュ関数」というとデータが文字列であるものを連想しやすいですが、 ここで扱う対象データは文字列ではありません。(ちなみに文字列のハッシュ関数は、異なる文字列が同じハッシュ値になることがあるので「完全」ではありません。)
さて、ここからが本題です。 組み合わせのデータを与えると整数を返すのがこのハッシュ関数でした。 この逆の関数、「整数xを与えると、hash(data) == xになるような組み合わせのデータdataを返す関数」を作ってください。
このお題はshuyoさんの提案を元に作成しました。ありがとうございました。
[ reply ]