組合せ最適化！

取り敢えずこの本には読書タグをつけておいたらしい。別のタグにしときゃいいけど、多分そんなに本なんて読まないしメモしない。

アウトラインというよりは、大事そうなところだけ拾い読みしてるっぽい雰囲気を出しつつメモ。(一応全部読んではいるけど、理解追いつかないしね。)あんま理解していないので、大雑把にしか書けない。

next permutation

順序付けが可能なデータの配列をもらったときに、その配列を辞書順で次に進めたい、というような状況。1,2,3->1,3,2->2,1,3->2,3,1->3,1,2->3,2,1という感じに。

基本的なアイディアとしては、昇順にソートされている場合は、多分後ろの方だけいじれば次に進める、的な感じ。実際には降順になっていない最短の部分配列を一番後ろの要素を含む連続な形で取り出す。そいつよりも大きいのが後ろに控えていることが分かったので、その中で一番小さいのと入れ変えれば辞書順で後ろのが得られるのが保証される。(すぐ次のじゃないけど。)後は他のやつらをソートしてやれば、すぐ次のが出てくる。確かに降順に全部並んでいるときには辞書順で次のが見つからないので、多分良さそう。

コードにするとこんな感じ。

boolean next_permutation(array[],size) {
  for(int i=size; i>1; --i) {
    if( array[i - 2] < array[i - 1] ) {
      int j = i;
      while( j < size && array[i - 2] < array[j] ) { ++j; }
      swap(array, i - 2, j - 1);
      for(int k=i-1,l=size-1; k<l; ++k,--l) { swap(array, k, l); }
      return true;
    }
  }
  return false;
}

スライド30枚くらい書いたんだけど、必要なのこれだけな気がする競技プログラマ...。