第９講　プロシージャの再帰的使用

第６話　プロシージャの再帰的使用による順列の作成
Form1

縦は長めにとってください。また、Form1のプロパティの配置のAoutoScroll

はTrueにしておいてください。例えば、７次順列は５０４０個の順列があるからです。
幾らForm1を長めにとっても、入りきらないのでスクロールできるようにしておくわけです。

コーティング例
Public Class Form1
　　 '変数の宣言と初期化
　　 Dim n, s As Integer
　　 Dim a(12) As Integer
　　 Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

　　　　　s = 0
　　　　　'順列次数取得
　　　　　n = TextBox1.Text
　　　　　'データグリッドビューのデータのクリア
　　　　　DataGridView1.Rows.Clear()
　　　　　f(0)
　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　DataGridView1(12, s + 1).Value() = s '総数表示

　　 End Sub

　　 Sub f(ByVal g As Integer)
　　　　　Dim h As Integer

　　　　　For i = 1 To n
　　　　　　　a(g) = i
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
　　　　　Next
　　 End Sub

End Class
拍子抜けするほど簡単です。
これで、7次であろうと12次であろうとできてしまうのです。
理論的は、何次でもできるコーティングなのです。実行例を示しましょう。

　　　　　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　　　　　・

とてもコーティングする気になりませんが、もしFor文版なら９次元ループです。
大変複雑になります。
それに対して、自己再帰版は至ってシンプルです。

それでは、解説に入りますが、今回も３次順列を例にとって説明します。
例えば８次順列では、トレースが膨大になってしまうからです。
プログラムコードを読む際に大切なことは、各変数の役割をしっかり把握することでしたね。
このコードではセル番号はgです。前のFor文に対応させてlでもよかったわけですが、
私が初めて作った魔方陣作成プログラムは、C言語によるものでした。
プログラムで作らせた魔方陣をディスプレイ（モニター）に表示させていたので、
画面位置のつもりでgとしていたのです。
以来、VBA等でもたくさん魔方陣作成プログラムを作ってきましたが、
ずっとgで通してきました。
魔方陣の場合セルは２次元ですが、２次元は１次元で表現できることは前に学習しました。
２次元セルを１次元番号gで整理するというアイディアは、私の魔方陣作成研究において、
時期を画するものでした。
魔方陣作成も、結局今挑戦している順列作成と原理的に同じであると気がついたことによって、
私の魔方陣研究は、爆発的に進展することになったのです。
そして、このアイディアは間違いなく時間割作成にも生かせます。
時間割作成は、２次元セルで縦横の条件があるという点で、
魔方陣作成とまったく同じであるからです。
半年ぐらい缶詰で研究開発の時間があれば、
完全な時間割作成ソフトができると思っています。
完全なというのは、市販されている時間割ソフトは例外なく出来が悪く、
かえって手で組んだ方が速い場合もあるぐらいです。
時間割ソフトで組めたとしても出来が悪すぎて、
結局時間割係の先生方が、何日も缶詰作業で手直しているのが現状です。
私は、いろいろと仕事ややりたいことがたくさんありますので、
時間割作成ソフトの開発に携わるつもりはありません。
やりたいことは、今行っている講座もひとつですが、
左脳一辺倒になっている現在の数学教育を根底からひっくり返すこと、
社会科学の方法について私の説を証明すること、
の２つも入ります。
この２つは、私のライフワークであると思っています。
そのほかの小さな夢としては、現在の数独問題作成ソフトVer.1を改良し、
より高速に、より難度が高い良問を作成できるようにすることもあります。

ごめんなさい。少し脱線しました。
ソフトハウスの方は、是非私の魔方陣作成ソフトを利用して完全な時間割ソフト開発していただければと思います。

さて、脱線は終了して解説に戻りましょう。
gはセル番号です。
For i = 1 To nのiが各セルに入る数字です。
前のFor文版では、３次配列の３に対応して３次元でｉ，ｊ，ｋが用意されましたが、
プロシージャの再帰的使用においては、１つでよいです。
理由は、プロシージャf(0)、f(1)、f(2)は入れ子式人形のそれぞれ異なる人形です。
セル番号gが異なれば、同じfでも次元の違うプロシージャなのです。
セル番号0なら、１次元目のループ、セル番号1なら２次元目のループ、セル番号2なら３次元目のループ
というわけです。ですから、For i = 1 To nのi1つで済むのです。
1つでセル番号gに応じて何次元ループでも可能なのです。



各変数の役回りが明確になったところで、トレースしてみましょう。
もう一度確認しますが３次順列で説明しますのでn=3です。
まず、
　　　　　f(0)
でg = 0でプロシージャfが呼び出されます。
n=3なので、

対象セルは３つです。プロシージャfの１次元ループが
　　　　　　　　　　　For i = 1 To n
１次元目ループ（セル番号０のループ）になります。
まず、１巡目でa(g) = i から、

が実現します。
g = 0ですから、条件
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
はあっさりクリアして、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が実行されます。g+1<nは1<3で条件を満たしますので、If文が実行されf(g + 1)によって、fが再帰的に呼び出されます。
fが自分自身を呼び出しています。ただし、呼び出しているfはf(0)であるのに対して、呼び出されるfはf(1)です。
入れ子式人形の、一番外側の人形がf(0)で、外側から２番目の人形がf(1)です。
つまり、入れ子式人形の一番外側の人形が外から２番目の人形を呼び出しているのです。
さて、f(1)の次元は

セル番号１の世界

です。
f(1)の
For i = 1 To n
によって

となります。そして、
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
によって、１と１が比較され内容が同じなのでh = 0となり、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
は実行されず、f(1)のループの２巡目になり、

今回は条件
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
をクリアして、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が実行されます。
g+1<nは、2<3なのでf(g + 1)が実行されf(2)が呼び出されます。
つまり、f(1)がf(2)を呼び出したのです。f(2)によって、セル番号２の世界

に入ります。言い換えれば、入れ子式人形の最後の人形の世界になります。

f(2)の
For i = 1 To n
によって

となります。g = 2なので、If文
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
が実行され、For文の1巡目によって、１と１の比較がなされますが、内容が同じで
h = 0となり、For文は強制的に終了となります。
したがって、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
は実行されず、f(2)の2巡目になり、

で
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の1巡目は１と２の比較でクリアしますが、２巡目において２と２の比較になり、内容が同じで
h = 0となってしまい、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
再び実行されず、f(2)の３巡目になり、

となります。今度は、
　　　　　　　h = 1
　　　　　　　If g > 0 Then
　　　　　　　　　For j = 0 To g - 1
　　　　　　　　　　　If a(j) = a(g) Then
　　　　　　　　　　　　　h = 0
　　　　　　　　　　　　　Exit For
　　　　　　　　　　　End If
　　　　　　　　　Next
　　　　　　　End If
の1巡目、２巡目において１と３、２と３が比較されますがいずれも内容が違っていて、
hは１のまま書き換えられず、
　　　　　　　If h = 1 Then
　　　　　　　　　If g + 1 < n Then
　　　　　　　　　　　f(g + 1)
　　　　　　　　　Else
　　　　　　　　　　　DataGridView1.Rows.Add() '１行追加
　　　　　　　　　　　For j = 0 To n - 1
　　　　　　　　　　　　　DataGridView1(j, s).Value = a(j)
　　　　　　　　　　　Next
　　　　　　　　　　　s = s + 1
　　　　　　　　　End If
　　　　　　　End If
が実行されますが、g+1<nは3<3で正しくないので、If文の方は実行されずElse文が実行され、
1個目の順列がデータグリッドビューに表示され、s = s + 1によって順列総数が１とされます。

解説が大分長くなりましたので以後のトレースは次話で。
次話で第９講は終了といたします。
次話が終わればいよいよ卒業研究と卒業試験を残すのみとなります。
卒業に向けてがんばりましょう。

第５話へ　第７話へ

VC++講義第１部へ
vb講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座

数学研究室に戻る