順列の列挙

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

(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).

の計24個あります。一般に,n個のものから,r個取ってできる順列の個数は,

n・(n−1)・・・(n−r+1)

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

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

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

1番目 2番目 3番目    
3通り 残り2通り 残り1通り    
123
132
213
231
312
321


のように,残った数字から,順次順列を作って行きます。最初はn通り,次はそれぞれn−1通りと,r回これを行いますから,すべての場合はn・(n−1)・・・(n−r+1)となります。

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

重複順列

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

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

の9個です。n個の中からr個取る重複順列の個数は nr です。ですから,上の場合3・3=9となります。

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


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

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

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

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

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

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


 

n と r を入力したとき,

n 個の中から,r 個取る重複順列をすべて列挙する

プログラムを書きましょう。

但し,0<r≦n<10とします。


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

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

例えば,上では,3個の中から2個とる重複順列は,

(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)

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

(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

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


一般に, 0から,n−1までのr 個の組はn進法数と考えると,0から,n−1までの数と丁度1対1に対応します。

 

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

(1)n と r の入力

For i=0 to n^r-1

    (2) iのn 進法展開の各桁を求めて,その組を表示する。

Next i

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

重複順列の中から順列を抽出

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

(1)n と r の入力

For i=0 to n^r-1

    (3) iのn 進法展開の各桁を求めて,その各桁が重複が無いかチェックする。
    そして,重複の無い組を表示する。

Next i

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

  1. ・n 進法展開の各桁を求めそれを,配列 P(j) (j=1からrまで)に入れます。
  2. ・P(j) (j=1からrまで)が重複がないか調べます。

となります。

 1は,i ,n,r が与えられたとき,iがn進でr桁の数であることを使うと,

Tmp =i
For j=1 to r
   P(j)=Tmp mod n
   Tmp = Tmp \ n
Next j

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

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

For j=1 to r
   If Fl(P(j))=1 then
      (*) 重複あり
   Else
      Fl(P(j))=1
   End If
Next j

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

Function IsPerm(i) as Boolean ' 重複ありのとき False,重複なし(順列になる)とき,True を返す。
   Tmp =i
   For j=1 to r
      P(j)=Tmp mod n
      Tmp = Tmp \ n
   Next j
   For j=0 to n-1 : Fl(j)=0 : Next j    ' Fl(j) の初期化
   IsPerm = True
   For j=1 to n
      If Fl(P(j))=1 then
         IsPerm = False
         Exit For
      Else
         Fl(P(j))=1
      End If
   Next j
End Function

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

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

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

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

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

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

10^8=100000000

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

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

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

樹形図の模倣

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

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

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

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

となっています。


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

その処理を仮に

Permutation(S,T,Num)

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

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

Permutation(S,T,1)

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

Permutation(S,T,2)

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

Permutation(S,T,r+1)

となると終了です。

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

Sub Permutation(S,T,Num)
   If Num=r+1 then
      順列作成終了:結果の書き出し
   Else
      S の各文字 Chに対して,T に Ch を付け加えてできる順列を T1,
      S から Ch を取り除いた文字の集合を S1 として,
           Permutation(S1,T1,Num+1) を実行する。
   End If
End Sub

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

1番目Permutaiton({1,2,3},{},1) 2番目 3番目    
3通り 残り2通り 残り1通り    

Permutaiton({2,3},{1},2)

Permutaiton({3},{12},3)

Permutaiton({},{123},4)
123

Permutaiton({2},{13},3)

Permutaiton({},{132},4)
132

Permutaiton({1,3},{2},2)

Permutaiton({3},{21},3)

Permutaiton({},{213},4)
213

Permutaiton({1},{23},3)

Permutaiton({},{231},4)
231

Permutaiton({1,2},{3},2)

Permutaiton({2},{31},3)

Permutaiton({},{312},4)
312

Permutaiton({1},{32},3)

Permutaiton({},{321},4)
321

となります。

プログラムへ

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

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

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

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


最初の版

Sub Permutation(Sa(),Ta(),Num)      ' Ta(Num) に文字を追加して順列を作る
   If Num=r+1 then
      WriteResult(Ta())                    ' 結果を書き出す Subプログラム
   Else
      For i=1 to N-Num+1
         Ta(Num) = So(i)                   ' So(i) に入っている文字をTa(Num) として追加
         So(i) と So(N-Num+1) と入れ替え
         Permutation(Sa(),Ta(),Num+1)
   End If
End Sub

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

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

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

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

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

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

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

第2の版

Sub Permutation(Sa(),Ta(),Num)      ' Ta(Num) に文字を追加して順列を作る
   If Num=r+1 then
      WriteResult(Ta())                    ' 結果を書き出す Subプログラム
   Else
      For i=1 to N-Num+1
         Ta(Num) = So(i)                   ' So(i) に入っている文字をTa(Num) として追加
         So() を保存
         So(i) と So(N-Num+1) と入れ替え
         Permutation(Sa(),Ta(),Num+1)
         So() の復元
   End If
End Sub

 

プログラム

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

Sub Permutation(So(),Ta(),Num)
   Dim SoTmp(MaxN),Tmp
   If Num=R+1 then
      ResultWrite(Ta())
   Else
      For i=1 to N-Num+1
         Ta(Num)=So(i)                  ' Num番目にi番目So(i)を代入
         If Num<=R then
            For j=1 to N-Num+1       ' So() を保存
               SoTmp(j)=So(j)
            Next j
            Tmp = So(N-Num+1)      ' So(i) と So(N-Num+1) との入れ替え
            So(N-Num+1)=So(i)
            So(i)=Tmp
         End If
 
         Permutation(So(),Ta(),Num+1)    ' 再帰

         If Num<=R then
            For j=1 to N-Num+1       ' So() を元に戻す
               So(j)=SoTmp(j)
            Next j
         End If
      Next i
   End if
End Sub

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

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

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

まとめ

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

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

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

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

と言えます。

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