並べ替えの最小移動回数

質問

1からnの番号のついたn個のものを１列に並べます。

その正しい並べ方が1,2,3,...,nだとします。

現在の並びが、適当なある並びだったときに、

最低、いくつの数字の場所を移動させると正しい並びになるか、その移動回数を求める方法をご存知の方がおられましたら教えてください。

たとえば、5つのものがあって、

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

1を先頭に移動することで、正しい並びになり、これが最短ですから、最小の移動回数は１回です。

また、3,1,4,2,5という並びでしたら、

1を先頭に移動し、2をその次に移動すれば正しい並びになりますから、最小の移動回数は２回です。

このように、n個のものの、任意の初期状態の並びに対して、それを正しい並びに変える最小の移動回数を求める方法はありますでしょうか？

回答No.6

pori_boy · ベストアンサー

こんばんは、No4で書き込んだものです

最長パスに関してご存知とのことなので、
証明できることの簡単な紹介だけ。

数字を1からn、最長の昇順部分列の長さをkとする。
このとき、n-k回が最小移動回数であることの証明：

[十分性] この部分列に含まれない要素（n-k個ある）を
順に適切な位置に挿入すると正しい並びになる。

[必要性] 背理法でしめす。もし、n-k-1回の移動で
正しい並びに直せるとすると、（少なくとも）k+1個の
要素は動かす必要がないことになる。これらは正しい
順列で昇順に並んでいるので、初めのならびでも昇順
にならんでいたことになる。これは最長昇順部分列の
長さがkであったことに矛盾する。

なお、他の方の回答に関して書き込んでよいのかどうか
わからないのですが、No5の方の方法に関して：
45123 では > は1箇所、最小移動回数は2 ですね。

不等号が > となる箇所の数は必須ですが、それで
十分とはいえない場合があります。

お礼

再びの丁寧なご回答ありがとうございます。

動かさない部分列は昇順に並んでいないといけないと言うのがポイントですね。

よくわかりました。

回答No.7

ryn

反例が出ちゃいましたね^^;

あの方法でいけたならプログラムもすごく楽そうだったのに…

お礼

そうですね。

そこまで単純にはならなくて、残念です。。。

回答No.5

ryn

> ３１４２５
> だと、上記を満たさないのは、
> ２と３の間だけとなり、
> 最少回数の２回と食い違ってしまうのです。
No.2 での回答はこの意味ではなく，
　a[i] > a[i+1]
のように i番目と i+1番目を比較します．

３１４２５の場合
　3 > 1
　1 < 4
　4 > 2
　2 < 5
のように，２箇所不等号が > となる場所があり，
最少回数の２回と同じになります．

お礼

再度のご回答ありがとうございます。

また、誤解してすみません。

たしかに、不等号が食い違っている箇所は、入れ替えが必須になりますね。

これで最少になることが確認できれば、完璧ですね。

回答No.4

pori_boy

移動しないものに着目すると、これらの数はもとの
順列において必ず昇順に並んでいる必要があります。
よって、与えられた順列から、最長の昇順部分列を
見つけることができれば解は求まります。
例えば、23451なら2345, 31425は345が最長部分列で
あり、これ以外のものが移動することになります。

この昇順の最長部分パスも求めるための方法ですが、
グラフ理論についての知識があれば、非巡回有向
グラフ上での最長パス問題に帰着されることが、
動的計画法をご存知でしたら、その手法によって
計算できることが説明できます。

sunasearchさんが、これらの知識をお持ちかどうか
わからないので、ひとまずここまでをアドバイスと。
もし、説明が必要でしたら、また書き込みます。

お礼

ご回答ありがとうございます。

＞最長の昇順部分列を見つけることができれば解は求まります。

これで、確かに最長パスを求めれば、最小の移動回数が求められる気がします。

最長パスは、最悪n^2オーダのアルゴリズムを組めば求められると思いますが、それを用いた移動回数が最小であることは保証されますでしょうか？

回答No.3

noborder

証明はしていませんが、以下でよろしいのではないのでしょうか？

n-1回

なお、ご質問の意図を整理すると、
『n個の数の並びで最も必要回数の多い場合についての、
　最少の移動回数』
を計算したいということでよろしいしょうか？

並べ替えに要する必要回数が多い場合は、まったく反対の並びになっていた場合だと思います。
5個の数なら
54321
が最も必要回数の多い場合です。

これを12345の順にするのに必要な回数は、5-1で4回です。

帰納的にそうなると思いました。学生をやめて時間が長いので、証明方法までは調べないと分かりませんが…

お役に立ったでしょうか？

お礼

ご回答ありがとうございます。

すみません。

＞『n個の数の並びで最も必要回数の多い場合についての、最少の移動回数』

ではなく、

『n個の数の並びの、ある特定の場合についての、最少の移動回数』

です。

回答No.2

ryn

まだちゃんと確かめていませんが，
　a[1],a[2],a[3],…,a[n]
と並んでいたときに
　a[i] > a[i+1]
となっている場所の個数を数えればよいのではないでしょうか．

お礼

ご回答ありがとうございます。

３１４２５

だと、上記を満たさないのは、２と３の間だけとなり、最少回数の２回と食い違ってしまうのです。

回答No.1

tatsumi01

この問題、配置位置は考えないのでしょうか。それだと簡単な問題ですが。
コンピュータの並べ替えではメモリ上での場所を考えます。2,3,4,5,1 という配置でしたら 1 を先頭に持って行くと 2 が邪魔で、よけないといけません。結局、作業メモリを１個取って、５＋１回の移動が必要ですね。3,1,4,2,5 でも 1 を先頭に持って行くとき 3 が邪魔になりますね。
以上は in place つまり同じ配列の中だけでやりくりする場合ですが、別に配列を用意するなら、移動回数は N 回です。

お礼

ご回答ありがとうございます。

配置位置は考えなくてかまわないです。

つまり、配列ではなくて、リスト構造になります。