Garbage Collection

塵も積もれば山

目次

Blog 利用状況

ニュース

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

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

書庫

日記カテゴリ

[数学]違うわ!よく聞け!こーやって並べ!

n個の物を順番に並べる時、並べ方は何通りあるか。
これは、n!で表せます。

これに番号をつけて管理する時、
ちょっと変わった進数表現をしてやればいいです。

1桁目は0,1だけ(2で繰り上がる)
2桁目は0,1,2だけ(3で繰り上がる)
3桁目は0,1,2,3だけ(4で繰り上がる)
4桁目は0,1,2,3,4だけ(5で繰り上がる)

こんな感じですね
0, 1, 10, 11, 20, 21, 100,
101, 110, 111, 120, 121, 200,
... , 300, 301, 310, 311, 320, 321, 1000

ちょっと不思議な感じですね

では、これを数字の列に直すとき、どうするか。
それぞれの桁数は挿入位置を表しています。
n桁目はn+1の数字の挿入位置です。

例として「310」ってのを4つの数字のならびに直してみましょう。

1桁目は0なので、2の挿入位置は0
2桁目は1なので、3の挿入位置は1
3桁目は3なので、4の挿入位置は3


ということで、2314という並びになるんですね。

ただ、この方法はすべての順列を作って何かをする、というのには向きません。
そういう場合は、直接配列を並び替えてやった方が速いです。

投稿日時 : 2008年7月23日 21:16

Feedback

# re: [数学]違うわ!よく聞け!こーやって並べ! 2008/07/24 11:15 シャノン

だんじょだんだんじょだんじょ…

# re: [数学]違うわ!よく聞け!こーやって並べ! 2008/07/24 23:51 NyaRuRu

Factoradic ですな.
http://en.wikipedia.org/wiki/Factoradic
http://msdn.microsoft.com/en-us/library/aa302371.aspx

こっちは Combinadic.
http://www.microsoft.com/japan/msdn/vs/vcsharp/mth_lexicograp.aspx

# [数学]最後尾はここではありません! 2008/07/25 0:27 Garbage Collection

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

タイトル  
名前  
Url
コメント