順列

異なるn個のものを並べます。その並べ方を全部書き出すプログラムを作ってみましょう。

まず，具体的に考えます。

a,b,c の３文字を並べ替えると

[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]

の６通りができます。

a,b,c,dの４文字を並べ替えたときはどうでしょう。

このとき，初めから考え直すのではなく，上の３文字の順列を利用することを考えるのです。

[a,b,c] の並びの両端と文字間の４箇所に d を入れていけば４通りの順列ができます。

他の並びについても同様にすれば，６×４=24通りの並びができますね。

これをプログラムします。

まず，[a,b,c] はリストとして処理できますので，このリストに１文字を追加する関数を作りましょう。

引数として，list と k,e を与えます。list の k番目に，要素 e を挿入するのです。

関数の中で新しいリスト（戻り値として使うので rt）を用意し，list の k-1 番目までをまずコピー（順に追加）します。

k番目に要素eを入れて，listのk番目からあとをさらに追加します。

=======================================

inslist(list,k,e):=(

  m=length(list);

  rt=[];

  repeat(k-1,s,rt=append(rt,list_s));

  rt=append(rt,e);

  repeat(m-k+1,s,rt=append(rt,list_(k+s-1)));

);

=======================================

戻り値は，最後に実行された rt=append(rt,list_(k+s-1))); のリストです。

次に，本体を作ります。perm(n)としましょう。

先ほど，３つの順列を利用して４つの順列を作りました。先ほどはa,b,cの文字でしたが文字だと追加する要素を決めにくいので，数字にします。

一般にn個の順列なら，n-1個の順列を利用することになります。

引数に n を与えて，まず n-1 個の順列を作るのです。

すると，順列を作る関数 perm(n) の中で perm(n-1)を実行することになります。

このような関数を「再帰的（リカージョン）」と言います。

さて，たとえば，n=4 にしたとき，perm(3) を実行しますが，その中では perm(2) を実行し，perm(2)の中では perm(1) を実行することになります。

どこかで止めないと無限に実行することになりますが，引数に０を与えるのは意味がないので，perm(1)で止めることにすればよいですね。

つまり，引数が n=1 のときはその結果：1つのものの順列：すなわち [[1]] を返すのです。リストのリストであることに注意してください。

すると，perm(2)では，[1]が返ってくるので，それに「2」を追加して[[1,2],[2,1]]ができます。

すると，perm(3)ではこれを利用して[[1,2,3],[3,1,2],[1,3,2],[2,1,3],[3,2,1],[2,3,1]] ができます。

最後に，これに 4 を追加したものができることになります。

=====================================

perm(n):=(

  if(n<2,ret=[[1]],

   ls=perm(n-1);

   ret=[];

   repeat(length(ls),s,

     ret=append(ret,append(ls_s,n));

     repeat(length(ls_s),t,

       ret=append(ret,inslist(ls_s,t,n));

     );

   );

  );

);

=====================================

 なお，リストの最初は，1,2,3,4 と順に並ぶものができるようにしています。

< 戻る >