順列組み合わせを表示

前田稔(Maeda Minoru)の超初心者のプログラム入門

プログラムの説明

1. 次のファイルを格納して下さい。
   

   /*********************************/ /*★ 順列を求める 前田　稔 ★*/ /*********************************/ using System; class Prog { const int NUM = 4; static int[] tbl = new int[NUM]; //★ MAIN PROGRAM public static void Main() { int i; for(i=0; i<NUM; i++) tbl[i]= i+1; jyun(tbl,NUM); Console.ReadLine(); } // 順列を求める static void jyun(int[] t, int n) { int i,k,w; if (n<2) { list(); return; } k= n-1; for(i=n-1; i>=0; i--) { w= t[k]; //t[k] と t[i] を入れ替える t[k]= t[i]; t[i]= w; jyun(t,k); t[i]= t[k]; //t[k] と t[i] を元に戻す t[k]= w; } } // 順列を List static void list() { int i; for(i=0; i<NUM; i++) Console.Write("{0} ",tbl[i]); Console.WriteLine(""); } }

2. 簡単そうに見えて意外と難しいのが「順列組み合わせ」の問題です。
   わがままな娘の願いで、クイズの問題を解くために作成したプログラムからの抜粋です。 (^_^;)
   １～４の数字の組み合わせで４桁の数列を表示する場合、２４通りの組み合わせが出来ます。
   今回も再起関数(自分自身を多重に呼び出す)を使います。
   
3. NUM が組み合わせに使う数字で、４の場合１～４の数字の組み合わせで４桁の数列になります。
   

   const int NUM = 4;

4. Main() では tbl[] に 1～NUM の値を格納して jyun() 関数を呼び出します。
   

   for(i=0; i<NUM; i++) tbl[i]= i+1; jyun(tbl,NUM);

5. jyun() が順列組み合わせを求める再起関数です。
   jyun 関数では数字を入れ替えて全ての組み合わせを求めます。
   jyun 関数の中から jyun 関数を呼び出していることに注目して下さい。
   

   for(i=n-1; i>=0; i--) { w= t[k]; //t[k] と t[i] を入れ替える t[k]= t[i]; t[i]= w; jyun(t,k); t[i]= t[k]; //t[k] と t[i] を元に戻す t[k]= w; }

6. list 関数は tbl[NUM] を表示する関数です。
   

【演習】

1 2 3 4 
2 1 3 4 
1 3 2 4 
3 1 2 4 
3 2 1 4 
2 3 1 4 
1 2 4 3 
2 1 4 3 
1 4 2 3 
4 1 2 3 
4 2 1 3 
2 4 1 3 
1 4 3 2 
4 1 3 2 
1 3 4 2 
3 1 4 2 
3 4 1 2 
4 3 1 2 
4 2 3 1 
2 4 3 1 
4 3 2 1 
3 4 2 1 
3 2 4 1 
2 3 4 1 

超初心者のプログラム入門(C# Frame Work)