Garbage Collection

塵も積もれば山

目次

Blog 利用状況

ニュース

C++とかC#とか数学ネタを投下していく予定です。

[その他のページ]
日々の四方山話を綴った日記出水の日記帳

書庫

日記カテゴリ

[数学]最後尾はここではありません!

前回の最後にちょっと書いた、配列を直接並び替える方法です。

1~5の並びを考える時、5桁の数とみなして考えます。
この5桁で、一番小さな数になる並びは、12345です。
ここからスタートして、次に大きな数をひたすら探していって、
もっとも大きな数になる、54321になるまで順にたどっていけばいいわけです。

どうやって、次に大きな数を探すかですが、
まず考えないといけないのは、
なるべく下の位だけを取り替えて上の位は触らない、ってことです。

では、12345の次の数を探しましょう。

まず、一番下の位の5を一時領域に置きます。
次の位は4が入っているので、5に置き換えます。
そして、5が入っていた所に4を置いて、12354が次に大きい数です。

12354の次も見てみましょう。

先ほどと同じように4を一時領域に置きます。
次の位は5ですが、4と交換してしまうと求める数が小さくなるので、
これもまた一時領域に置きます。
次は3で4か5と交換できますが、3より大きくて一番小さい4と交換します。
最後に空白に3と5を並べるわけですが、35と53だと35の方が小さいので
35を置いて、12435が次に大きい数になります。

まとめると、
・一時領域に自分より大きい数がなければ、一時領域に移動。
・一時領域に自分より大きい数があれば、その数と交換。
 候補が複数あれば、候補の中で一番小さい数にする。
・交換が出来たら、空白に一時領域の数を小さい順に並べる。

なお、この方法だと、1122という風に、同じ数が複数あってもいけます。
自分より大きい数を探してくるので、重複するパターンを2度数えることもありません。

#手書きメソッド結構お気に入り…汚い字だから読みにくいかな?

投稿日時 : 2008年7月25日 0:27

Feedback

# re: [数学]最後尾はここではありません! 2008/07/25 6:15 επιστημη

ぁぃ、このアルゴリズムがまんまnext_permutationで実装されちょりますですねぃ。

# re: [数学]最後尾はここではありません! 2008/07/25 9:52 シャノン

走らないでくださーい。走らないでくださーい。走るなっつってんだろそこぉ!

# re: [数学]最後尾はここではありません! 2008/07/25 22:00 出水

やっぱり、next_permutationの中身はこんな感じですか
比較演算子さえ実装していれば数値じゃなくてもいいところがいいですね

サークルで中にいると10時ごろに津波が押し寄せてきます、怖い怖い

# [C#]組み合わせ小細工 2009/01/29 16:11 Garbage Collection

[C#]組み合わせ小細工

タイトル  
名前  
Url
コメント