C言語での順列生成プログラムの実装例と説明

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関数の挙動

1. 標準入力から生成する順列N!の値Nを読み取る

2. 順列をストックするための配列Pをmallocで動的確保する

3. 一つの順列の中で、既に使われた数をトラックするための配列usedをmallocで動的確保する

4. 配列を生成する関数permutationsに先ほど確保した配列のPとused、そして配列の合計のNと現在の配列の番地を指し示すNを引数として渡す

5. 動的確保した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の値の異なる順列を表示

という流れとして再帰されて順列が生成されます。