ここでは，順列の列挙について考えます。順列はいくつかの文字を順序を考慮して並べたものです。文字がどのようなものであるかは重要でないので，ここではまず，数字１からｎまでを使った順列を考えましょう。例えば，１から４の数字から，３個とる順列は

(1,2,3), (1,2,4), (1,3,2), (1,3,4), (1,4,2), (1,4,3),
(2,1,3), (2,1,4), (2,3,1), (2,3,4), (2,4,1), (2,4,3),
(3,1,2), (3,1,4), (3,2,1), (3,2,4), (3,4,1), (3,4,2),
(4,1,2), (4,1,3), (4,2,1), (4,2,3), (4,3,1), (4,3,2).

の計２４個あります。一般に，ｎ個のものから，ｒ個取ってできる順列の個数は，

ｎ・（ｎ－１）・・・（ｎ－ｒ＋１）

個あります。ですから，上の場合，４・３・２＝２４個になります。このことは高校の教科書にも載っていますし，証明も難しくはありません。ですから，この個数を求めることは問題ではありません。ここではこれらの順列を実際にすべて列挙してみることを考えます。

　また列挙も概念的には特に難しいものでもありません。普通は樹形図というものを使って求めます。

　例えば，３個のものから，３個取る順列をすべて作るには，

のように，残った数字から，順次順列を作って行きます。最初はｎ通り，次はそれぞれｎ－１通りと，ｒ回これを行いますから，すべての場合はｎ・（ｎ－１）・・・（ｎ－ｒ＋１）となります。

　手で列挙する場合は，これを実際に行えば良いわけですが，プログラムに書くとするとどうすれば良いでしょう？

　 普通の順列の他に，重複順列があります。順列は同じ文字を２個以上使わないという条件で作りましたが，この条件をつけない順列を重複順列と言います。例えば，３個の中から２個とる重複順列は，

(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)

の９個です。ｎ個の中からｒ個取る重複順列の個数は　ｎ^ｒです。ですから，上の場合３・３＝９となります。

そこで，まず，重複順列を列挙することを考えて見ましょう。すぐに気がつくように，重複順列を列挙するのは，簡単です。すべての場合をそのまま組み合わせれば良いだけだからです。

　例えば，上の，３個の中から２個とる重複順列をすべて表示するプログラムは，

For i=1 to 3
    For j=1 to 3
        Print "(";i;;",";j;")"
    Next j
Next i

で実現できるでしょう。しかし，この実現方法は，少し問題があります。

例えば，９個の中から，５個取る重複順列を列挙するプログラムをこの方法で，書くとどうなるでしょうか？

For i1=1 to 9
    For i2=1 to 9
        For i3=1 to 9
            For i4=1 to 9
                For i5=1 to 9
                    Print "(";i1;;",";i2;",";i3;",";i4;",";i5;")"
                Next i5
            Next i4
        Next i3
    Next i2
Next i1

　このような感じでしょうか。このプログラムも確かに動きますし，この問題であればこれでも良いのですが，次のような問題が与えられたら，どうでしょうか？

但し，０＜ｒ≦ｎ＜１０とします。

　この但し書きの条件は本質的ではありませんが，パソコンと Tiny Basic の能力からすれば，現実的な条件です。

　上のプログラムを変更しようとすると，この問題はとても難しいと思われるかもしれませんが，視点を少し変えると，決して難しいものではありません。そのため，今迄，１からｎまでの数を扱いましたが，０からｎ－１の数を扱うことにします。これは，文字を１つ入れ替えただけですから，順列の構成には重要ではありません。

例えば，上では，３個の中から２個とる重複順列は，

(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)

としましたが，これを

(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)

として考えます。この組に対して，各成分を３進法での桁と見なして，数に対応させます。つまり，

(0,0)=0×3+0=0,
(0,1)=0×3+1=1,
(0,2)=0×3+2=2,
(1,0)=1×3+0=3,
(1,1)=1×3+1=4,
(1,2)=1×3+2=5,
(2,0)=2×3+0=6,
(2,1)=2×3+1=7,
(2,2)=2×3+2=8,

によって対応を考えると，

(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)

が

0, 1, 2, 3, 4, 5, 6, 7, 8

と９個の数に丁度１対１に対応することが分かります。

一般に， ０から，ｎ－１までのｒ 個の組はｎ進法数と考えると，０から，ｎ^ｒ－１までの数と丁度１対１に対応します。

このように考えると，上の問題は簡単な問題になります。つまり，次のようなプログラムで実現されます。

ここで，(1)と(2)は適当な方法で実現するものとします。これを実際に実現したプログラムRPermutation.tbtはここにあります。

　順列を列挙する最も素朴な方法は，重複順列の中から順列を抽出していくものでしょう。上のプログラムで既に，重複順列を すべて求めていますから，それらのうちで，重複がないものを取り出せば，良いわけです。この方法によると，これは次のように実現されます。

ここで(3)の実現方法を考えて見ます。この処理を２つの部分に分けると，

1. ・n 進法展開の各桁を求めそれを，配列 P(j) （ｊ＝１からｒまで）に入れます。
2. ・P(j) （ｊ＝１からｒまで）が重複がないか調べます。

となります。

　１は，i ，n，ｒ が与えられたとき，iがｎ進でｒ桁の数であることを使うと，

とすれば，P(j) に各桁が入ります。（順序は左から小さい桁が入っています。）

　２は，この数字が使われたかどうかの判定をするために，配列 Fl(1),...,F(n) を用意します。初期値はすべて，ゼロとします。iが使われたとき，Fl(i)=1 とすることにします。既に，Fl(i)= 1 である i があれば，重複ありとなります。

これらを合わせて，i を入力したとき，それらの桁に重複があるかないかを返す関数を書いて見ます。
　

このプログラムを完成させたPPermutaion.tbtはここにあります。

このプログラムは比較的簡単ですが，よく考えると効率はあまりよくありません。

　実際，ｎとｒが大きくなるにつれて，かなりの時間がかかります。もちろん，個数自身大きくなりますから，時間がかかるのは当たり前ですが，その個数に比例するよりも，時間が掛かります。

　この問題は具体例を見ると良く分かります。例えば，１０個の中から，８個取る順列を列挙することを考えましょう。これは，

10×9×8×7×6×5×4×3＝1814400

個の順列があります。他方，実際は一度重複順列を列挙しますから，

10^8＝100000000

個の順列を作っていることになります。ですから，実際は100000000/1814400≒５５倍の計算をしています。

　この比はｒが大きくなるにつれて，大きくなります。

何か良い別の方法はないでしょうか。

　普通，手で順列を列挙するには上に説明したように，樹形図を使います。この樹形図の考え方は，効率的で，重複順列を列挙するような過程を含んでいません。そこで，この樹形図を使った方法で，プログラムを書くことにしましょう。

　樹形図の考え方は，既に使った文字を取り除いた文字の中から，新たに使う文字を選びます。

即ち，樹形図の各ステップは，

• 既に得られた順列に，使える文字をその順列に付け加えて，新たな順列を作ると言うものです。
• そして，そのようにして得られた順列に対して，同様な処理を施し，
• 必要な長さの順列が得られるまで続ける

となっています。

　再帰を使うと，この様な処理を比較的簡単に実現できます。そこで以下，再帰を使ってこの処理を実現します。

その処理を仮に

Permutation(S,T,Num)

と名づけます。これは，S に含まれる文字を１つ順列 T に付け加え新たなNum文字からなる順列 T を作るものです。

ここで，最初， S は使う文字すべての集合， T は空の順列を表すとすると，

Permutation(S,T,1)

は樹形図の第１ステップを行うものとし，1個の元からなる順列を作った後，その各々の順列に対して

Permutation(S,T,2)

を実施し，この処理を以下同様に繰り返し，r が求める順列の長さとすると，

Permutation(S,T,r+1)

となると終了です。

この処理をアルゴリズムとして纏めると，

となります。これを，３個のものから，３個取る順列を作る例について実行すると，

となります。

　上のアルゴリズムを実際のプログラムにして見ましょう。Tiny Basic では集合や順列自身を対象とすることは出来ませんので，それらをそれぞれ配列 So(N)と Ta(N) を使います。So の配列に入っている文字を使って Ta の配列に順列を作ります。これらの配列を Sub プログラムに引き渡す場合，配列引渡しを使いましょう。

　So(N) から１つの文字を取り除く処理は，使った文字を最後に移動して，残った文字数を１つ減らすと言うことで実現します。

この考えで，プログラムを作ると次のようになるでしょう。

　ここで，N と r は Public 宣言をされているものとし， N 個のものから r個取る順列を作るものとします。

最初の版

　ここで，N-Num+1 は使える文字の個数で，使える文字は So(1) から So(N-Num+1) に入っています。

　これで大体良いのですが，配列変数引渡しの場合の重要な注意があります。

配列変数引渡しは，配列自身全部を引き渡します。

ですから引き渡されたプログラムでその値を変更すると，元の配列も変更されてしまいます。

従って，配列変数引渡しの先で，その配列が変更される場合は，引渡す前に，その値を保存して，戻ったときそれを復元する必要があります。

今の場合， Ta() については，変更されても，戻る過程で値が設定されますから，保存の必要がありませんが，So() については保存の必要があります。

　それを考慮すると，次のようになります。

第２の版

以上のことを考慮して，纏めると次のようになります。

　このプログラムでは Soを保存するため，配列 SoTmp を定義しています。この変数は配列引渡しをしないので，保存されます。

Dim SoTmp(MaxN) での MaxN はPublic Const　として定義されているものとします。

　これを使ったプログラム Permutaion.tbt はここにあります。

　順列の列挙は原理的には難しいことはありませんが，効率的にそれを列挙するにはそれなりの工夫が必要です。

重複順列の中から順列を抽出 するプログラムと，再帰を使ったプログラムの速度は違いは歴然です。小さな数については余り違いはありませんが，ｒが５程度でも違いははっきりと分かります。

　計算機は多くの処理は高速に行うものですが，それでも扱いたい量に比べて不十分であることは多々あります。そして時には工夫によってそれを改良することもできます。もちろん原理的に高速化が不可能なこともありますが，それでも多くの場合，改良の試みをする価値はあります。

プログラムの高速化はアルゴリズムの改良で！

と言えます。

　順列の列挙の応用例が欲しいと思う人もいるでしょう。１つの応用として覆面算があります ので参考にして下さい。