回答受付が終了しました
1からNまでの数で順列をつくるとき、横並びにしてばいけない数の組み合わせ(e.g. [2,3],[4,5])が与えられた場合、考えうる順列の並び方の数を求める方法について。
1からNまでの数で順列をつくるとき、横並びにしてばいけない数の組み合わせ(e.g. [2,3],[4,5])が与えられた場合、考えうる順列の並び方の数を求める方法について。 難しい関数はなしで、アルゴリズムでアドバイスを貰えないでしょうか。 よろしくお願いします。
回答（2件）
■ まず確認ですが 例えば N=5, [2,3], [4,5]が与えられたとき 1 2 3 4 5や3 2 4 1 5などはダメだけど 2 5 3 4 1などのOKな順列はいくつあるか 答え：48個 というような問題の考え方ですよね？ ■ 横並びにしてはいけない数の組み合わせの与え方を制限しないと 簡単なアルゴリズムを見つけることは困難です。 なぜなら、この問題はハミルトン路問題よりも難しい問題だからです 実際、N頂点のグラフの各頂点を数1,2,3,...,Nに対応させて 辺が無い頂点を横並びにしてはいけない数の組と見なします。 すると、ハミルトン路問題は 「そもそも条件を満たす順列があるのか無いのか」という 質問の問題よりも少し簡単そうな問題と同じものだと分かります ■ 横並びにしてはいけない数の組（禁止ペアと呼ぶことにします） の与え方によっては簡単に求まる場合もあります 例えば 質問の[2,3], [4,5]のように 禁止ペアどうしで含む数が被らないような場合です このような場合は包除原理で簡単に求められます m個の禁止ペアが与えらえたときの個数は Σ[k=0, m] mCk×((-1)^k)×(2^k)×(N-k)! で求められます 例えば質問の例でN=5なら Σ[k=0, 2] 2Ck×(-1)^k×2^k×(5-k)! = 5!-2×2×4!+4×3! = 120-96+24 = 48個 です 簡単に言うと N!個の順列から与えられた禁止ペアを含む順列を除いた個数 を求めるという方法です
[5,5]とかはok？ とりあえず適当にやるなら forを二重に回して i=1〜n, j=i+2〜n-2とします すると、[1,3],…,[n-2,n]という左側が小さく条件を満たすものを全て得ることが出来ますよね？ そして、総数としてはその×2です。左と右を入れ替えればええので。 なのでその個数の×2を出力すればよろしい。 [k,k]とかもカウントするなら、さっきの合計に+nすればよろしいです
1人がナイス！しています
