1 順列

平成15年度横浜国立大学工学部編入試験に出題された問題である。

1.1 問題

$N$個の要素を持つ文字形の配列a[]が与えられているとする。このとき、a[0]〜 a[N-1]の要素を並べ替えて得られる$N!$個の順列を全て印刷するプログラムについ て以下の問に答えなさい。

なお、a[]〜a[N-1]に対する全ての順列を生成するという作業は、a[N-1] の要素をa[0]〜a[N-1]のいずれか一つの要素と交換したN通りの状況に対して、 それぞれ、a[0]〜a[N-2]の順序を全て生成することによりなされる点に注意す ること。

[問1]

下記プログラムが目標となるように、空欄 〜 を埋めなさい。 ただし、下記プログラムにおいてNの値は3である。

[問2]

完成したプログラムの出力結果を示しなさい。ただし、複数行の出力が印 刷される場合には、各行の時間順序も正しくないといけません。

#include <stdio.h>
#define N (3)

char a[N]={'a', 'b', 'c'};

main()
{
  perm(a, N);
}

perm(char a[], int n)
{
  int i;

  if(n <= 1)
    print_a(a, N);
  else
    for(i=0; i <n; i++){
      swap(a, i, n-1);

perm(a, n-1);
swap(a, , );

    }
}

swap(char a[], int i, int j)
{
  char c;

  c=a[i];

a[i]= ;
a[j]= ;

}

print_a(char a[], int n)
{
  int i;

  printf("%c", a[0]);
  for(i=1; i<n; i++)
    printf(" %c", a[i]);
  printf("\n");
}

1.2 解答

このプログラムは、再帰呼び出しを用いて、順列を全て書き出している。プログラム中の 関数perm()の動作は、次のようになっている。

• 第二引数により与えられる値は、順列を求める範囲を示す。例えば、第二引数が nとすると、a[0]〜a[n-1]までの全ての順列を求め表示する。
• ただし、表示は0〜a[n-1]までは全ての順列を表示するが、a[n]〜 a[N-1]は変化せず、元のままである。

このような関数を再帰呼び出しを使って、a[0]〜a[N-1]までの順列を表示すれ ばよい。そのためには、次のようにする。

• a[N-1]の要素をa[0]〜a[N-1]の全ての順列を書き出す。
  • そのためには、a[N-1]の要素をa[0]〜a[N-1]のいずれか 一つの要素と交換しする。
  • a[0]〜a[N-2]の全ての順列を書き出す。ここで再帰呼び出しを 使う。
  • a[N-1]の要素を戻し、次の要素に進む。

この再帰呼び出しが終了する条件は、呼び出しの第二引数nが1の場合である。この 場合は、一通りしかないので、画面に出力する。

ざっと、プログラムは、こんな感じである。以下に解答を示すので、よく理解せよ。

[問1]

以下の通りにすれば、再帰呼び出しを用いた、順列の組み合わせを出力す るプログラムになる。
n-1
n-1
i
a[j]
c

[問2]

プログラムの出力は以下の通り。

		b c a
		c b a
		c a b
		a c b
		b a c
		a b c

ホームページ: Yamamoto's laboratory
著者: 山本昌志