「今週のお題：並べ替えの繰り返し2」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 空白区切りで入力される2数m,n ( m≦9 ) に対して、1～mのm枚のカードを横一列に並べる並び方のうち、次の条件を満たす場合の数を出力する
  • その条件とは、左端のカードの数字に対して、その数字の枚数分、左端から並ぶカードを左右反転する時、n回丁度の反転で左端に 1 が来ること

例えば、5,3,1,4,2 という並びであれば、

  • 5,3,1,4,2 → 2,4,1,3,5 ( 全て反転 ) → 4,2,1,3,5 ( 2,4の2枚反転 ) → 3,1,2,4,5 ( 5以外反転 ) → 2,1,3,4,5 ( 3,1,2の3枚反転 ) → 1,2,3,4,5 ( 2,1の2枚反転 )

のように5回で左端に1が来ます。

解説

今回、なかなかうまい方法が思い浮かびませんでした。

そうかといって、最大でもm=9だから並び方を9!≒36万通り単純に試そうか、とも思ったのですが、それは流石にRubyでは時間がかかり過ぎるようでした。( 或いはC/C++なら何とかなったかもしれませんが )

単純に全検索すると時間がかかる要因としては、本質的に同じパターンであるものを重複して調べることになるというのが1つあります。どういうことかと言うと、次に挙げる例として、

  • 4,3,1,2,6,5 → 2,1,3,4,6,5 → 1,2,3,4,6,5
  • 4,5,1,2,3,6 → 2,1,5,4,3,6 → 1,2,5,4,3,6
  • 4,6,1,2,5,3 → 2,1,6,4,5,3 → 1,2,6,4,5,3
  • …

これらは全て2回で1が来るものですが、実は 4,x,1,2,x,x という形であれば、x の部分に関係なく同じように2回で1が来ています。つまり、このパターンでは x の箇所の数に応じた 3!=6通りの重複があるということです。

そこで、左端に1が来ているパターンから遡っていき、本質的に同じパターンをまとめられるように列挙していくことを考えました。

以下Rubyでの実装です。

# 階乗
ff,fm=->n{fm[n]||=n*ff[n-1]},[1,1]
p ->m,n{
  # 条件を満たすパターンの配列
  # 各要素は、数字の配置 ( 未確定部分はnil )、未使用の数字のbit-set、未使用の数字の数の組
  # 数字は0～m-1で考える
  a=[[[0,*[nil]*(m-1)],(1<<m)-2,m-1]]
  n.times{
    a=a.each_with_object([]){|(f,b,r),c|
      # 回数の1つ小さいパターンを元に、先頭に来る数字毎にパターンを登録
      (1...m).each{|i|
        if !f[i]
          # ひっくり返す場所の数字が未知ならば、未使用の場合のみ登録
          if b[i]==1
            t=f.dup
            t[1..i]=t[0...i].reverse
            t[0]=i
            c.push([t,b&~(1<<i),r-1])
          end
        elsif f[i]==i
          # ちょうどひっくり返す位置の数字であれば、未使用の数字を使わない
          t=f.dup
          t[0..i]=t[0..i].reverse
          c.push([t,b,r])
        end
      }
    }
  }
  # 各パターン、未使用の数字の数の階乗通りずつカウント
  a.reduce(0){|s,r| s+ff[r[2]] }
}[*gets.split.map(&:to_i)]

配列のインデクス操作が分かり易くなるように、1～m の代わりに 0～m-1 を使って、0,x,x,… というパターンから遡ります。1手遡った時に左端がどうなるかに応じてパターンを分岐していきます。

例えば、冒頭に挙げた

  • 5,3,1,4,2 → 2,4,1,3,5 → 4,2,1,3,5 → 3,1,2,4,5 → 2,1,3,4,5 → 1,2,3,4,5

であれば、1～5 の代わりに 0～4 なので

  • 4,2,0,3,1 → 1,3,0,2,4 → 3,1,0,2,4 → 2,0,1,3,4 → 1,0,2,3,4 → 0,1,2,3,4

という遷移になるのですが、逆向きに辿って都度未知の部分を解決していき

  • 0,x,x,x,x → 1,0,x,x,x → 2,0,1,x,x → 3,1,0,2,x → 1,3,0,2,x → 4,2,0,3,1

と反転を繰り返しながらパターンを構築していきます。これは各ステップで、1→2→3→1→4 を左端に来る数として選択することに対応します。

各ステップで、まだ左端に来たことのない数を選ぶと、未知の数が減っていくことになります。そこで、未知の数をbit-setで管理します。最後にパターン数を数える時には未知の数の種類が影響しますから、個数も一緒に管理します。
なお、1度選んだ数が再び左端に来ることもあり得ます。その場合は未知の数の個数は変化させません。いずれにせよ、反転させた場合に不整合が発生するパターンは省いていきます。

終わりに

反転させる度に、その区間にあるパターンがひっくり返ってしまうので、なかなか静的な解析ができず苦労しました。ということでパターンを地道に探すことに。もっと良いやり方はないものでしょうかね。