読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第85回「隣り合えないカップル」

CodeIQというサイトで問題に挑戦した記録です。

https://codeiq.jp/sites/default/files/styles/thumb_175x114/public/engineer/algorithm.jpg?itok=Z_awtPsU

問題文を要約すると下記の通り、

  • {n}組のカップルを男女交互に円形に並べる事を考える。
  • カップルが隣同士に並ばないパターンの総数を解答する。
  • 円形なので回転したものは同じと見なすが、逆順は別とカウントする。
  • {n \leq 7}

方針

メモ化再帰を用いる
人数{n}人の女子を円形に並べ、その間にカップルが隣りあわない様に{n}人の男子を並べる配置を考える。
女子の組{\{g0,g1...g(n-1)\}}と添え字番号が同じ男子の組{\{b0,b1...b(n-1)\}}をカップルとして、添え字{i}{i+1} ( {n-1}番目は{n-1}と1周して{0})以外の位置に男子{bi}を配置する全パターンをメモ化再帰により数える。
これに、女子の円順列の総数{(n-1)!}を掛けて解答とする

f:id:ibeckuu:20160323012059j:plain

提出したコード (Ruby)

数学的な解法

上記のコードを提出した後、色々と調べてこの問題が「menage problem」(正しくはフランス語表記)という数学の典型問題だと知った。
下記の英語のページに式の記載があるが簡単な式ではなかった。ご参考まで
Menage problem
では、

Sponsored Link