順列を一瞬で取得するプログラム
こんにちわ。いたかなやです。
今日も来て頂いてありがとうございます。
今日は「順列」について少し考えてみたいと思います。
たとえば、「ABCD」のように4つのアルファベットの並べ方は、
4!(=4×3×2×1=24)通りあります。
この24個を全て書き出してみます。
(後の説明の関係上0番目から始めています。)
0番目:ABCD
1番目:ABDC
2番目:ACBD
3番目:ACDB
4番目:ADBC
5番目:ADCB
6番目:BACD
7番目:BADC
8番目:BCAD
9番目:BCDA
10番目:BDAC
11番目:BDCA
12番目:CABD
13番目:CADB
14番目:CBAD
15番目:CBDA
16番目:CDAB
17番目:CDBA
18番目:DABC
19番目:DACB
20番目:DBAC
21番目:DBCA
22番目:DCAB
23番目:DCBA
このように、アルファベットの若い方を優先的に並べていく順序を
「辞書式順序」といいます。
全てを書き出そうとする場合は、辞書式順序のように、ある一定の規則に従って書き出していかないと、重複が生まれてしまいそうですね。
さらに、上の例において、n番目の順列をすぐに取得する方法を考えてみます。
たとえば、13番目の順列を取得するには、
0番目 , 1番目 , ・・・という風に順番に書き出していかなくても、
すぐに、13番目の順列を取得する方法があるんです。
■「ABCD」を辞書式順序に並べた時に13番目の順列を取得する方法。
①13を1で割り、その答えを2で割る・・・のように4までこの計算を続けます。
13÷1=13・・・0
13÷2=6・・・1
6÷3=2・・・0
2÷4=0・・・2
②上の計算の余りに注目し、次のようにアルファベットを選んでいきます。(0番目から数えている点に注意して下さい。)
余り:2,0,1,0
「ABCD」の2番目のアルファベットを取得 → C
「ABD」の0番目のアルファベットを取得 → A
「BD」の1番目のアルファベットを取得 → D
「B」の0番目のアルファベットを取得 → B
以上です。
①②の要領で取得した順列「CADB」が上で紹介した辞書式順序の13番目の物と等しくなっていると思います。
それでは、例題をどうぞ。
「ABCDEF」の6つのアルファベットを
(0番目から)辞書式順序に並べた時に308番目の順列を答えなさい。
【解答】
308÷1=308・・・0
308÷2=154・・・0
154÷3= 51・・・1
51÷4= 12・・・3
12÷5= 2・・・2
2÷6=0・・・2余り:2,2,3,1,0,0
「ABCDEF」の2番目→C
「ABDEF」 の2番目→D
「ABEF」 の3番目→F
「ABE」 の1番目→B
「AE」 の0番目→A
「E」 の0番目→Eよって、求める順列は「CDFBAE」
証明は簡単です。
最初の「ABCD」の例で考えてみましょう。
24通りの順列を下のように分類してみます。
A◯◯◯・・・3!=6通り
B◯◯◯・・・3!=6通り
C◯◯◯・・・3!=6通り
D◯◯◯・・・3!=6通り
それぞれ、◯◯◯の部分の並べ方が3!=6通りあるので、
このような形になります。
さらに、A◯◯◯の部分はこのようになっています。
AB◯◯・・・2!=2通り
AC◯◯・・・2!=2通り
AD◯◯・・・2!=2通り
もちろん、B◯◯◯・C◯◯◯・D◯◯◯も同様に並んでいる事がわかります。
次に余りを計算した部分です。
13(番目)という数字を1・2・3・4と割ってき、
《2,0,1,0》という余りを算出しました。
13÷1=13・・・0
13÷2=6・・・1
6÷3=2・・・0
2÷4=0・・・2
これを逆から考えると、
13=1×(2×(3×(4×0+2)+0)+1)+0
というようになっています。
さらにこれを展開すると、
13=4!×0+3!×2+2!×0+1!×1+0
つまり、これは、
13(番目)という数字の中には、
(i) 4!が0個←当たり前
(ii) 3!が2個
(iii) 2!が0個
(iv) 1!が1個
(v) 最後に0個←とりあえず無視
というように読む事ができます。
順番に見ていきましょう。
(i)すべてで、4!通りしかないのですから当たり前です。
(ii)3!が2個含まれるということは、A◯◯◯・B◯◯◯のゾーンを通り過ぎて、答えがC◯◯◯ゾーンにある事を示しています。
(iii)C◯◯◯ゾーン内で、2!が0個という事は、CA◯◯ゾーンである事が分かります。
(iv)CA◯◯ゾーン内で、1!が1個という事は、CAB◯ゾーンを通り過ぎて、CAD◯ゾーンである事が分かります。
(v)とりあえず無視というか、CAD◯ゾーンというか、もう残っているのはCADBです。
証明というか、仕組みの解説は以上です。
つぎにコードです。
(アルファベットでは無く数字を並べるようになっています。)
// n個の数字の順列において、辞書式順序のm番目を戻す function permutation(n,m){ var temp = new Array(); for(var i=0;i<n;i++)temp[i]=i; var surplus = new Array(); for(var i=1;i<n;i++){ surplus[n-i]=m%i; m=Math.floor(m/i); } surplus[0]=m; var order = new Array(); for(var i=0;i<n;i++){ order[i]=temp[surplus[i]]; for(var j=surplus[i];j+1<n;j++)temp[j]=temp[j+1]; } return order; }
これを見ると当たり前といえば当たり前なんですが、
n個のアルファベットの順列を0〜(n!−1)の数字に対応させる所に凄みがあると思いませんか。
今更か!と言われるかもしれませんが、ちょっと感動したので書き留めておきます。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ株式会社
- 発売日: 2013/12/04
- メディア: Kindle版
- この商品を含むブログ (2件) を見る
- 作者: グレッグイーガン,Greg Egan,山岸真
- 出版社/メーカー: 早川書房
- 発売日: 1999/10
- メディア: 文庫
- 購入: 22人 クリック: 238回
- この商品を含むブログ (213件) を見る
- 作者: グレッグイーガン,Greg Egan,山岸真
- 出版社/メーカー: 早川書房
- 発売日: 1999/10
- メディア: 文庫
- 購入: 15人 クリック: 49回
- この商品を含むブログ (157件) を見る
数学読本〈4〉数列の極限,無限級数/順列・組合せ/確率/関数の極限と微分法
- 作者: 松坂和夫
- 出版社/メーカー: 岩波書店
- 発売日: 1990/04/27
- メディア: 単行本
- 購入: 6人 クリック: 8回
- この商品を含むブログ (3件) を見る
- 作者: エム・アクセス
- 出版社/メーカー: 認知工学
- 発売日: 2008/10
- メディア: 単行本
- クリック: 9回
- この商品を含むブログを見る