数的全排列--深度优先搜索

矫情吗；* 2022-06-02 06:47 181阅读 0赞

*  例如：12的全排列是12、21，123的全排列是123、132、213、231、312、321。依次类推：1234的全排列是………  
    ![69743010.jpg][]
 *  在123 的全排列中，我们使用3个盒子存放即将放进的数字，每当走到一个盒子前就把手中的数字放进去，手中的数字没了之后，再次返回，把盒子中的数字拿走，再次进行排列。如此复杂的排列，如何使用程序解决呢？
 *  首先应该使用一个数组book来标记哪些牌已经使用了。

for(i=1;i<=n;i++){
           if(book[i]==0){
             a[step]=i;
             book[i]=1;
           }
        }

*  深度度优先搜索（Depth First Search ，DFS）的关键在于解决“当下该如何做”，至于“下一步如何做”则与“当下该如何做”是一样的。发明深度优先算法的是John E.Hopcroft(约翰.霍普克罗夫特)和RobertE.Tarjan(罗伯特.陶尔扬)。1971-1972他们在斯坦福大学研究图的连通性和平面性的边相互不交叉。在电路板上设计布线的时候，发现的这个奇妙的算法。
 *  程序代码如下：

#include<iostream>
    using namespace std;
    int a[10],book[10],n;
    void dfs(int step){
        int i;
        if(step==n+1){
            for(i=1;i<=n;i++){
                cout<<a[i];
            }
            cout<<endl;
            return ;
        }
        for(int i=1;i<=n;i++){
            if(book[i]==0){
                a[step]=i;
                book[i]=1;
                dfs(step+1);
                book[i]=0;//这一步非常重的，一定要将刚才尝试的扑克牌收回，才能进行下次的尝试。
            }
        }
    }
    int main(){
        cin>>n;
        dfs(1);
    }

[69743010.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-6/69743010.jpg