最近Cousera Algorithms Part Iをやっています。今の所難しすぎず、知っているかもなというテーマの部分でも学ぶことが多くてかなり面白いです。

今回はassingment 2の方針について書いてみます。

Randomized Queue

問題設定

• size: 要素数の取得
  
• enqueue: itemの追加
  
• dequeue: ランダムに選んだ要素の取得と削除
  
• sample: ランダムに選んだ要素の取得
  
  

という操作をconstant amortized timeで行えるRandomized Queueというデータ構造を実装しようという問題です。

方針

dequeueを高速に行うにはrandom accessができる必要があるので要素の管理をするのは配列がよさそうです。特定indexまで密でさえあってくれれば、そのindexまでの一様乱数生成1回で要素が選べます。できればdequeueをしたあとでも特定indexまで密である状態が維持されると理想的です。これはdequeue時に選んだ要素の位置に、要素を含む最大indexの要素を移動させることで維持できます。

配列の伸縮に関しては、ハッシュテーブルのtable doublingのようにフルになったら ~2n かけて倍に伸ばす、1/4が満たされた状態にまで減ったら ~2n で半分のサイズに縮める、ということをしていけばconstant amortized timeにできます。

感想

最初は、deuqueもしくは伸長してしてできる穴の部分をstackで管理してeuqneue時に使うという方法を考えました。dequeueで要素を選ぶときにも最悪でも1/4が埋まった状態なので、要素があるindexを引くまで繰り返しても回数の期待値は4回でこちらでもconstant amortized timeでいけます。上の方針のほうが空間効率も時間効率もシンプルさも良いですが。

できたと思ってもコーナーケースでミスりまくるので正しく動くプログラムを書くのは本当に難しいです。

Permutation

問題設定

n要素の入力と、整数k $(0 \leq k \leq n)$が与えられたときに、ぴったりk要素からなるランダムなsequenceをO(n)で返してほしいという問題です。
extra challengeは、最大でもk要素までのRandomizedQueueを使って実現してみましょうというものです。

方針

まず単純にはn要素をRandomizedQueueに入れて、k回dequeueすれば良いです。

extra challengeを考えてみます。
理想的には各要素が確率 $\frac{k}{n}$ で選ばれてそれがランダムな順序で返されると良いです。
各要素を最初から確率 $\frac{k}{n}$ で入れるかどうかを決めていくというのでは、常にぴったりk要素が得られません。

k要素までは何もせずに入れて、その後k要素を維持しながらうまくやれないかを考えてみます。
確率 $p(i)$ で $i$ 番目の要素を入れるとします $(i \gt k)$。
$i$ 番目の要素が最終的に残る確率を $P(i)$ とすると、残るのは $i$番目を入れ($p(i)$)、かつ$i+1$ を入れることになってdequeueで $i$番目の要素が選ばれない($p(i+1) \frac{k-1}{k}$)、もしくは $i+1$を入れない($1- p(i+1)$)、かつ $i+2$以降…なので

もし $1 - \frac{p(i)}{k} = \frac{q(i-1)}{q(i)}$ というような形にできると

なので、最終的には

• k番目の要素まではそのままenqueue
  
• それ以降はi番目の要素を確率 $\frac{k}{i}$ でdequeueとenqueue
  
  

ということをすればよさそうです。

感想

結果がシンプルのなのでもっとシンプルに考えられそうな気がします。