1つずつの組み合わせオブジェクトの総数をランダムに計算する定理はありますか？

Question

一般的なアルゴリズム的な課題は、特定の種類の物体を均一にランダムに生成することである。たとえば、 $ k $ のランダムな置換を生成します。 $ n $ この質問

。

そのような作業を解くとき、コンビナトリアルオブジェクトの数を再発関係を介して計算するための任意のアルゴリズムを Generate に変換することができることに気づいた。コンビナトリアルオブジェクト私の質問は、このテクニックの名前がありますか？これが本当のときに言う定理はありますか？

例えば、 $ 1のランダムな順序を生成したいとします。 $ sおよび $ 0 $ s。隣接する2つの $ 1 $ s。 $ a [n] $ $ をそのようなシーケンスの数にすることから始めます。 $$ A [N]= A [N - 1] + A [N - 2]。 $$

（これはフィボナッチ関係です。） これにより、 $ a [i] $ の表を効率的に計算できます。 $ i= 1 $ $ i= n $ 。 私がそのような順序をランダムに生成したいのなら、私がしなければならないのは：

ステップ1：ランダム値を生成します $ r $ から $ 1 $ $ a [n] $ 。

ステップ2： $ r $ sシーケンスに対応する副項を見つけるために再発関係を使用します。 >

• $ r \ lea [n-1] $ の場合、 $ r $ < / SPAN> $ a [n-1] $ によってカウントされ、 $ 0 $ を追加しました。

• $ a [n-1] の場合 $ R '= R - A [N-1] $ 、そして $ r' $ を再帰的に見つける $ a [n-container "$ によってカウントされ、 $ 01 $ を追加しました。

ここで起こっているように思われるものは、 $ a [n] $ の再発関係を考えると、これを返す再帰的アルゴリズムに変換することができます。 $ r $ $ a [n] $ によってカウントされます。これがよく知られていると思いますので、これについての参照または古典的な結果にも興味があります。特に、これは $ a [n] $ に特有のものではありませんが、特定の繰り返し関係を満たすの場合は真であるべきです。プロパティ

また、これはランダムテストに関する研究に関連している可能性があると思います。

Answer 1

これらはランキングおよび回復機能。カウントおよびアンランキングアルゴリズムのための繰り返し関係の間の対応についての正しい。