C語言全排列回溯算法介紹

Posted on by

前言

本博文源於最近學習的遞歸算法，遞歸中遇到一個問題全排列的問題，我看見回溯特別神奇，特此記錄一下。對比一下深度優先搜索與廣度優先搜索，個人感覺這裡的回溯像是一種遞歸樹中的深度優先搜索的算法，他不斷構造往下延伸的深度，使其達到完全編列

算法思想

比如3拿來舉例，按照一般正常的話就是應該，

123 132 213 231 312 321

六種，先造出一個hashtable數組讓其存儲在各位是否使用，然後創建path的p數組將數字進行選填，遞歸樹我花在文章下面。

在這裡插入圖片描述

完整代碼

#include<cstdio>
const int maxn = 11;
//P 為當前排列 HashTable記錄整個數x是否已經在P中
int n,P[maxn],hashTable[maxn] = {false};
//當前處理排列的第index位置
void generateP(int index) {
    if(index == n+1){
        for(int i=1;i<=n;i++){
            printf("%d",P[i]);
        }
        printf("\n");
        return ;
    }
    for(int x = 1;x<=n;x++) {
        if(hashTable[x] == false) {
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);
            hashTable[x] = false;
        }
    }
}
int main()
{
    n = 3;
    generateP(1);
    return 0;

}

實驗效果

在這裡插入圖片描述

總結

到此這篇關於C語言全排列回溯算法介紹的文章就介紹到這瞭,更多相關C語言全排列算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：