読者です 読者をやめる 読者になる 読者になる

目標は商店街をつくる事なんです。

あきらめてるわけじゃないんです。今やっていることが、必ず力になると思うんです。

順列を一瞬で取得するプログラム

こんにちわ。いたかなやです。

今日も来て頂いてありがとうございます。

f:id:itakanaya9:20140217025922p:plain

今日は「順列」について少し考えてみたいと思います。

たとえば、「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・・・
  13÷2=6・・・
  6÷3=2・・・
  2÷4=0・・・


②上の計算の余りに注目し、次のようにアルファベットを選んでいきます。(0番目から数えている点に注意して下さい。)
  余り:2,0,1,0
  「ABCD」の番目のアルファベットを取得 → C
  「ABD」の番目のアルファベットを取得 → A
  「BD」の番目のアルファベットを取得 → D
  「B」の番目のアルファベットを取得 → 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÷=13・・・
  13÷=6・・・
  6÷=2・・・
  2÷=0・・・

これを逆から考えると、

13=×(×(×(×0+)+)+)+

というようになっています。
さらにこれを展開すると、

13=4!×0+3!×2!×1!×

つまり、これは、

13(番目)という数字の中には、
(i) 4!が0個←当たり前
(ii) 3!
(iii) 2!
(iv) 1!
(v) 最後に個←とりあえず無視

というように読む事ができます。
順番に見ていきましょう。

(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)の数字に対応させる所に凄みがあると思いませんか。

今更か!と言われるかもしれませんが、ちょっと感動したので書き留めておきます。



プログラマの数学

プログラマの数学

順列都市〈上〉 (ハヤカワ文庫SF)

順列都市〈上〉 (ハヤカワ文庫SF)

順列都市〈下〉 (ハヤカワ文庫SF)

順列都市〈下〉 (ハヤカワ文庫SF)

数学読本〈4〉数列の極限,無限級数/順列・組合せ/確率/関数の極限と微分法

数学読本〈4〉数列の極限,無限級数/順列・組合せ/確率/関数の極限と微分法

書き上げて解く順列 (思考力算数練習張シリーズ 23)

書き上げて解く順列 (思考力算数練習張シリーズ 23)