第９講関数の再帰的使用第４話関数の再帰的使用によるｎ次順列生成解説その1

第９講関数の再帰的使用
第４話関数の再帰的使用によるｎ次順列生成解説その1
コード再掲
#include<iostream>
using namespace std;
void f(int g);
void h();
int x[15],n;
long cn;
void main(){
　　 cout<<"何次順列を生成しますか？"<<endl;
　　 scanf("%d",&n);
　　 cout<<endl;
　　 cn=0;
　　 f(0);
　　 cout<<n<<"次順列が"<<cn<<"個生成されました。"<<endl;
}
void f(int g){
　　 int i,j;
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
　　　　　　　 }
　　　　　}
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
　　　　　tobi:;
　　 }
}
void h(){
　　 for(char i=0;i<n;i++)cout<<x[i]<<" ";
　　 cout<<endl;
}
それでは、
上のコードでなぜｎ次順列が生成できるのかを解説していきましょう。
魔方陣数独で学ぶ VBA 入門でもこの話題に触れていますので、
再利用させて頂きます。

ｎ＝３の場合で解説していきます。
このコードを理解するためには、gとiの役割の違いを理解することです。
void f(int g){
　　 int i,j;
　　 for(i=1;i<n+1;i++){
　　　　　x[g]=i;
　　　　　if(g>0){
　　　　　　　 for(j=0;j<g;j++){
　　　　　　　　　　if(x[g]==x[j])goto tobi;
ｇはセル（枠）番号で、左から何番目のセル（枠）かを表す数です。
ただし、1番左のセルは０番目と数えています。
セルを比喩で次元と呼んだり、世界と呼んだりしますと、
gはパラレルワールドの次元番号をして示していることになります。
gが異なれば世界＝次元が異なる世界です。
そして、
次元（セル）が違えば、同じｉでも次元０のｉと次元１のｉと次元２のｉは別物です。

０	１	２
ｉ	ｉ	ｉ

ｉとｉとｉは別次元の世界の住民です。

少しむずしい言い方をしてしましましたが、簡単に言い直すと、
０，１，２はセル（数字や文字を入れる箱）のラベル名（箱の名前）であり、
ｉとｉとｉはそのラベルの貼ってあるセル（数字や文字を入れる箱）の内容です。
ｉとｉとｉは、１，２，３と動き、現象的には０，１，２と似ていますが、
実際には、ビール瓶の例えでは０，１，２はビール瓶のラベルですし、
ｉとｉとｉはビール瓶に入っているビールで、全然違うものです。
セル番号ｇとセルの中身ｉとｉとｉを明確に区別されてコードを読んでください。

ライラの冒険では、
主人公の女の子はあちらこちらの次元の世界を行ったり来たりしますが、
このプログラムも、いろいろな次元を行ったり来たりします。
今どの次元にいるのか、入れ子式人形例えでは、
外側から何番目の人形のところにいるのかを明瞭・明確に理解していないと、
訳がわからなくなります。
比喩で、

０	１	２
ｉ	ｉ	ｉ

と書いていますが、本当はfor文ループ版のときと違い、

０

０	１
2	3

０	１	２
3	1	2

と時に応じて様々な姿をしています。
関数は、呼び出されたときだけメモリー上に存在しています。
関数が活動を終えたとき、関数はメモリー上から消滅します。
変数と同じで、関数もメモリー上に存在していて、
メモリー上で生成消滅を繰り返すのです。
まず、mainから、f (0)で呼び出されて、はじめて世界

０

ｉ

が生まれます。そして、f (0)からf (1)が呼び出されたとき、２番目の世界

０	１
ｉ	ｉ

が生誕します。そして、f (1)からf (2)が呼び出されて、３番目の世界

０	１	２
ｉ	ｉ	ｉ

が発生します。f (2)が任務を遂行し終わると、f (2)は消滅して

０	１
ｉ	ｉ

となります。
同様に、f (1)も処理を終えると、命も終わり

０

ｉ

となります。
さらに、f (0)が任務を遂行すると、すべて消えてしまします。
しかし、f (0)・f (1)・f (2)が消滅しても、
生きていたときの活動結果がコンソールに残されるわけです。
つまり、
f (0)・f (1)・f (2)はコンソールに順列をすべて表示させるという任務を終えると、
消滅することが運命づけられているわけです。
順列の生成は、f (0)・f (1)・f (2)の連係プレイによるものですが、
コンソールに結果を表示させるという栄誉ある任務を遂行できるのは
（最後の核ボタンを押す権限をもつのは)、f (2)だけです。
　　　　　if(g+1<n){
　　　　　　　 f(g+1);
　　　　　}
　　　　　else{
　　　　　　　 h();
　　　　　　　 cn++;
　　　　　}
比喩による説明は以上にして、
次話では具体的にトレースしていきます。

第３話へ　第５話へ

 魔方陣数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
 ＶＢ講義基礎へ
 初心者のための世界で一番わかりやすいVisual C++入門基礎講座
 初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
 初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門基礎から応用まで第１部
eclipse java 入門
 java 入門サイト基礎から応用まで
VC++ C言語 C++ 入門初心者基礎から応用まで
本サイトトップへ