C言語での順列生成プログラムの実装例と自分なりのわかりやすい解説をまとめました。
順列生成とはつまりN!通りの順列を全て表示させるプログラムです。
AtCoderの過去問を解いているときに、C言語における順列の生成法が分からなかったので調べたのですが、それでもわかりにくかったので自分で書きました。
C言語での再帰の順列生成プログラムの実装例
#include <stdio.h>
#include <stdlib.h>
void permutations(int *P, int *used, int total, int N)
{
int i;
int n;
i = 1; //as permutation does not contain 0
while (i <= total)
{
if (!used[i]) //if i is unused in the current permutation
{
used[i] = 1; //mark i as "used"
P[N] = i;
if (N == 1) //print when one permutation is complete
{
n = total;
while (n)
{
printf("%d ", P[n]);
n--;
}
printf("\n");
}
else // set num for P[N - 1]
permutations(P, used, total, N - 1);
used[i] = 0; //set i as "unused"
}
i++;
}
}
int main()
{
int N;
int *P;
int *used;
printf("total num : ");
scanf("%d\n", &N);
P = (int *)malloc(sizeof(int) * (N + 1));
used = (int *)calloc((N + 1), sizeof(int));
permutations(P, used, N, N);
free(P);
free(used);
return (0);
}
以下で簡単にコードの説明をしています。
main関数の挙動
- 標準入力から生成する順列
N!の値Nを読み取る - 順列をストックするための配列
Pをmallocで動的確保する 一つの順列の中で、既に使われた数をトラックするための配列
usedをmallocで動的確保する配列を生成する関数
permutationsに先ほど確保した配列のPとused、そして配列の合計のNと現在の配列の番地を指し示すNを引数として渡す動的確保した
Pとusedをfree関数で開放する
(注意）2と3の時N + 1分の配列を確保しているのは、参照している値をわかりやすくするために、順列に含まれない0を飛ばしてそれぞれP[1]、used[1]から配列を使用しているためです。
(追記）
usedの配列が０で初期化されていなかったので、mallocの代わりにcallocを使用してはとのアドバイスをいただきました。ありがとうございます！usedの配列はcallocを使って確保するように書き換えました。
permutations関数の挙動
この関数は再起的に呼び出されることによって順列を生成しています
イメージとしては以下の画像のようになります。
全体の流れとしては、
1. まず再帰の最下層であるN = 1まで進み、その時点で完成されたPが表示される
2. 使用されていたiが解放され、N = 2の層に戻る(N = 1ではi = totalのためwhileループから抜けるから）
3. この時点で、i = totalになるまでwhileループに入っているので、まずP[2]とP[1]の値が入れ替わったものが次に表示される。
4. 使用されていたiが解放され、N = 3の層に戻る(N = 1とN = 2ではi = totalのためwhileループから抜けるから）
5. この時点でwhileループが終わるまでiの値の異なる順列を表示
という流れとして再帰されて順列が生成されます。