回溯法之排列树

参考文章

当所给问题是从n个元素的集合S中找出满足某种性质的排列时，解空间为排列树。例如：旅行售货员问题

  回溯法搜索排列树的描述为：

     void backtrack(int  t)
    {

       if(t>n)  
           output(x);
       else      
          for(int i=t; i<=n; i++) //这里的n表示层数，不要和子集树搞混了
          {
            swap(x[t], x[i]);
            if(constraint(t) && bound(t))      backtrack(t+1);
            swap(x[t], x[i]);       
         }     
   }

 

 

#include <>
#include <>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

void printVector(vector<int> array );

void dfs(vector<int>& array, int t)
{

    size_t size =  ();
    //只有满足t==size才可以输出
    if(t == size)
        printVector(array);

    //dfs to the next level
    for(int i = t; i < size; i++)
    {
       swap(array[t],array[i]);
       dfs(array, t+1);
       swap(array[i],array[t]);
    }

}


void printVector(vector<int> array )
{
    for(int i = 0; i <(); i++)
        cout << array[i]<< "\t" ;
    cout << endl;
}
//dfs(b,t),t的值决定了对t之后的数进行全排列,当t为0时是全部,t为1时是第一个数字之后
int main()
{
    vector<int> b;
    int i;
    for(i=1;i<=5;i++){
        b.push_back(i);
    }
    dfs(b, 0);
    return 0;
}

 

 

打印结果

5 6 7 8
5 6 8 7
5 7 6 8
5 7 8 6
5 8 7 6
5 8 6 7
6 5 7 8
6 5 8 7
6 7 5 8
6 7 8 5
6 8 7 5
6 8 5 7
7 6 5 8
7 6 8 5
7 5 6 8
7 5 8 6
7 8 5 6
7 8 6 5
8 6 7 5
8 6 5 7
8 7 6 5
8 7 5 6
8 5 7 6
8 5 6 7