C言語による全順列のための再帰的探索法

9か月 ago

芽依, 雨夜

1 minute

再帰を使って順列を求めるバックトラック法を実装できます。その方法は次のとおりです。

再帰関数　backtrack()　を定義する. 引数は, 配列 nums (並べ替える対象) と, 配列 path (現在までに並べた部分的な並び)
backtrack()関数においてまず部分的な並びが配列の長さになったかを判定し、配列の長さに達していたらその並びを結果に加える。
未確定の順列が配列の長さ未満なら、まだ使用していない配列中の要素をすべて試し、各要素を未確定の順列の最後に追加して使用済みとマークしたのち、再帰的に backtrack() 関数を呼び出して残りの要素の順列を続ける。
再帰呼び出しの後に、現在の部分的な並びを過去の状態に戻す必要があります。これは、最後に加わった要素を削除し、その要素を未使用としてマークして、次の利用可能な要素を試すことができるようにします。
最後に、主関数でバックトラック関数を呼び出し、初期パラメータを渡します。

再帰バックトラック法による順列の生成コード例を以下に示します。

#include <stdio.h>
#include <stdbool.h>
// 数组长度
#define N 3
// 标记数组，标记元素是否已使用
bool used[N];
// 全排列结果集
int res[N];
// 回溯函数
void backtrack(int nums[], int depth) {
// 如果已排好的部分排列达到了数组的长度，输出结果
if (depth == N) {
for (int i = 0; i < N; i++) {
printf("%d ", res[i]);
}
printf("\n");
return;
}
// 遍历数组中尚未使用的元素
for (int i = 0; i < N; i++) {
if (!used[i]) {
// 将尚未使用的元素加入到部分排列的末尾
res[depth] = nums[i];
used[i] = true;
// 递归调用，继续排列剩下的元素
backtrack(nums, depth + 1);
// 将部分排列恢复到之前的状态，以便尝试下一个可用的元素
used[i] = false;
}
}
}
int main() {
int nums[N] = {1, 2, 3};
backtrack(nums, 0);
return 0;
}

以下のコードを実行すると、次の出力が得られます。

以上は、再帰バック・トラッキング法を使用して全順列を実現する方法です。