順列を一瞬で取得するプログラム - 目標は商店街をつくる事なんです。

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

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

f:id:itakanaya9:20140217025922p:plain

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

たとえば、「ABCD」のように４つのアルファベットの並べ方は、
４！（＝４×３×２×１＝２４）通りあります。

この２４個を全て書き出してみます。
（後の説明の関係上０番目から始めています。）

０番目：ABCD
１番目：ABDC
２番目：ACBD
３番目：ACDB
４番目：ADBC
５番目：ADCB
６番目：BACD
７番目：BADC
８番目：BCAD
９番目：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番目の順列を取得するには、
０番目 , １番目 , ・・・という風に順番に書き出していかなくても、
すぐに、13番目の順列を取得する方法があるんです。

■「ABCD」を辞書式順序に並べた時に13番目の順列を取得する方法。

①13を１で割り、その答えを２で割る・・・のように４までこの計算を続けます。
　　13÷１＝13・・・０
　　13÷２＝６・・・１
　　６÷３＝２・・・０
　　２÷４＝０・・・２

②上の計算の余りに注目し、次のようにアルファベットを選んでいきます。（０番目から数えている点に注意して下さい。）
　　余り：２,０,１,０
　　「ABCD」の２番目のアルファベットを取得　→　C
　　「ABD」の０番目のアルファベットを取得　→　A
　　「BD」の１番目のアルファベットを取得　→　D
　　「B」の０番目のアルファベットを取得　→　B

以上です。
①②の要領で取得した順列「CADB」が上で紹介した辞書式順序の13番目の物と等しくなっていると思います。

それでは、例題をどうぞ。

「ABCDEF」の６つのアルファベットを
（０番目から）辞書式順序に並べた時に308番目の順列を答えなさい。

【解答】
308÷１=308・・・０
308÷２=154・・・０
154÷３= 51・・・１
51÷４= 12・・・３
12÷５= 2・・・２
2÷６=０・・・２
余り：２,２,３,１,０,０
「ABCDEF」の２番目→C
「ABDEF」の２番目→D
「ABEF」の３番目→F
「ABE」の１番目→B
「AE」の０番目→A
「E」の０番目→E
よって、求める順列は「CDFBAE」

証明は簡単です。
最初の「ABCD」の例で考えてみましょう。
２４通りの順列を下のように分類してみます。

A◯◯◯・・・３！＝６通り
B◯◯◯・・・３！＝６通り
C◯◯◯・・・３！＝６通り
D◯◯◯・・・３！＝６通り

それぞれ、◯◯◯の部分の並べ方が３！＝６通りあるので、
このような形になります。

さらに、A◯◯◯の部分はこのようになっています。

AB◯◯・・・２！＝２通り
AC◯◯・・・２！＝２通り
AD◯◯・・・２！＝２通り

もちろん、B◯◯◯・C◯◯◯・D◯◯◯も同様に並んでいる事がわかります。

次に余りを計算した部分です。
１３（番目）という数字を１・２・３・４と割ってき、
《２,０,１,０》という余りを算出しました。

　　13÷１＝13・・・０
　　13÷２＝６・・・１
　　６÷３＝２・・・０
　　２÷４＝０・・・２

これを逆から考えると、

１３＝１×（２×（３×（４×０＋２）＋０）＋１）＋０

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

１３＝４！×０＋３！×２＋２！×０＋１！×１＋０

つまり、これは、

１３（番目）という数字の中には、
(i)　４！が０個←当たり前
(ii)　３！が２個
(iii)　２！が０個
(iv)　１！が１個
(v)　最後に０個←とりあえず無視

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

(i)すべてで、４！通りしかないのですから当たり前です。
(ii)３！が２個含まれるということは、A◯◯◯・B◯◯◯のゾーンを通り過ぎて、答えがC◯◯◯ゾーンにある事を示しています。
(iii)C◯◯◯ゾーン内で、２！が０個という事は、CA◯◯ゾーンである事が分かります。
(iv)CA◯◯ゾーン内で、１！が１個という事は、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;
}