重み一定符号化

study

先日の問題の一部をどう書く？orgで見つけた.
「組合せ型の最小完全ハッシュ関数」の逆関数 どう書く？orgが下のdecodeの話になっている.
パスカルの三角形をテーブルで持つとnがでかいときに遅すぎる. Fishcer and Sternのアルゴリズム *1 を実装して投稿した.
暗号の立場から言うと一部のナップサック暗号やNTRUを実装する時に必要になる関数.

ウォーミングアップ

俺が知っている問題から一つ. 暗号に使われるので知っている.
長さnのビット列の中でも1の個数がちょうどmのものを考える. S(n,m)=\{x \in \{0,1\}^n | \sum_i x_i = m\}とする.
するとS(n,m)の要素数は\left(\begin{array}{c}&n\\&m\end{array}\right)である.

問題:

以下の二つのプログラムを与えよ.

  • encode
    • 入力: x \in S(n,m)
    • 出力: i \in \{1,...,\left(\begin{array}{c}&n\\&m\end{array}\right)\}
  • decode
    • 入力: i \in \{1,...,\left(\begin{array}{c}&n\\&m\end{array}\right)\}
    • 出力: x \in S(n,m)

*1:元論文のアルゴリズムをベタに実装すると上手く動かないよ