今天主要是想回憶下DFS，所以就那全排列開刀了，自己寫了一個發現網上的解法真不錯就想總結下：
一、利用DFS實現（自己寫的）
廢話就不說了 上代碼：
#include <iostream>
#include <cstdio>
using namespace std;
const int size = 20;
bool visited[20];
int arr[20];
int n;
void dfs(int cnt)
{
if( cnt == n)
{
for(int i = 0; i < n; ++i)
{
cout << arr[i] << " " ;
}
cout << endl;
}
else
{
for(int i = 1; i <= n; ++i )
{
if(!visited[i])
{
arr[cnt] = i;
visited[i] = 1;
dfs(cnt+1);
visited[i] = 0;
}
}
}
}
int main()
{
while(cin>>n)
{
memset(visited, 0, sizeof(visited));
dfs(0);
}
return 0;
}
這種方法,我沒有想好怎么實現含有相同元素的全全排列
二、利用遞歸實現，其實還是DFS，只是實現的方法不一樣，但是它能夠實現含有相同元素的全排列
下面給一段網上找的解釋，其實王曉東的那本《算法與設計》有這個：
令E={e1,e2...en}表示n個元素的集合，我們的目標是生成該集合的所有排列方式。令Ei為E中移去元素i以后所獲得的集合,perm（X）表示集合X中元素的排列方式，ei.perm(X)表示在perm(X)中的每個排列方式的前面均加上ei以后所得到的排列方式。例如，如果E={a,b,c},那么E1 = {b,c},perm(E1) = (bc,cb),e1.perm(E1) = (abc,acb)。
對于遞歸的基本部分,采用n=1。當只有一個元素時,只可能產生一種排列方式,所以perm(E) = (e)，其中e是E中的唯一元素。當n>1時，perm(E) = e1.perm(E1) + e2.perm(E2)+ e3.perm(E3）+.......+en.perm(En)。這種遞歸定義形式是采用n個perm(X)來定義perm(E)，其中每個X包含n-1個元素。至此，一個完整的遞歸定義所需要的基本部分和遞歸部分都已完成。
下面給出我自己寫的代碼：
#include <iostream>
#include <cstdio>
using namespace std;
template<class T>
void sswap(T &a, T &b)
{
if( a != b )
{
int tmp = a;
a = b;
b = tmp;
}
}
template<class T>
void Perm(T list[], int k, int m)
{
if(k == m)
{
for(int i = 0; i <= m; ++i)
{
cout << list[i] << "";
}
cout << endl;
}
else
{
for(int i = k; i <= m; ++i)
{
// if( (list[k] != list[i]) || (k == i) ) //為了實現相同元素的全排
// {
sswap(list[k], list[i]);
Perm(list, k+1, m);
sswap(list[k], list[i]);
//}
}
}
}
int main()
{
int n;
int arr[10];
while(cin>>n)
{
for(int i = 0; i < n; ++ i)
{
cin>>arr[i];
}
Perm(arr, 0, n - 1);
}
return 0;
}
三、壓軸：STL next_permutation
下面是網上的一段分析
C++/STL中定義的next_permutation和prev_permutation函數則是非常靈活且高效的一種方法，它被廣泛的應用于為指定序列生成不同的排列。本文將詳細的介紹prev_permutation函數的內部算法。
按照STL文檔的描述，next_permutation函數將按字母表順序生成給定序列的下一個較大的排列，直到整個序列為降序為止。prev_permutation函數與之相反，是生成給定序列的上一個較小的排列。二者原理相同，僅遍例順序相反，這里僅以next_permutation為例介紹算法。
先對序列大小的比較做出定義：兩個長度相同的序列，從兩者的第一個元素開始向后尋找，直到出現一個不同元素（也可能就是第它們的第一個元素），該元素較大的序列為大，反之序列為小；若一直到最后一個元素都相同，那么兩個序列相等。
設當前序列為pn，下一個較大的序列為pn+1，這里蘊藏的含義是再也找不到另外的序列pm，使得pn < pm < pn+1。
問題
給定任意非空序列，生成下一個較大或較小的排列。
過程
根據上述概念易知，對于一個任意序列，最小的排列是增序，最大的為減序。那么給定一個pn要如何才能生成pn+1呢？先來看下面的例子：
設3 6 4 2為pn，下一個序列pn+1應該是4 2 3 6。觀察第一個序列可以發現pn中的6 4 2已經為減序，在這個子集中再也無法排出更大的序列了，因此必須移動3的位置且要找一個數來取代3的位置。在6 4 2中6和4都比3大，但6比3大的太多了，只能選4。將4和3的位置對調后形成排列4 6 3 2。注意，由于4和3大小的相鄰關系，對調后產生的子集6 3 2仍保持逆序，即該子集最大的一種排列。而4是第一次移動到頭一位的，需要后面的子集為最小的排列，因此直接將6 3 2倒轉為2 3 6便得到了正確的一個序列pn+1。
下面歸納分析該過程。假設一個有m個元素的序列pn，其下一組較大排列為pn+1：
若pn的最后的2個元素構成一個最小的增序子集，那么直接反轉這2個元素使該子集成為減序即可得到pn+1。理由是pn和pn+1的前面m-2個元素都相等（沒有對前面的元素進行操作），僅能靠最后2個元素來分出大小。而這2個元素只能出現2種排列，其中較大的一種是減序。
若pn的最后最多有s個元素構成一個減序子集，令i = m - s，則有pn(i) < pn(i+1)，因此若將pn(i)和pn(i+1)調換必能得到一個較大的排列（不一定是下一個），因此必須保持pn(i)之前的元素不動，并在子集{pn(i+1), pn(i+2), ..., pn(m)}中找到一個僅比pn(i)大的元素pn(j)，將二者調換位置。此時只要得到新子集{pn(i+1), pn(i+2), ..., pn(i), ...,pn(m)}的最小排列即可。注意到新子集仍保持減序，那么直接將其反轉即可得到最小的增序子集。
按以上步驟便可從pn得到pn+1了。
復雜度
最好的情況為pn的最后的2個元素構成一個最小的增序子集，交換次數為1，復雜度為O(1)，最差的情況為1個元素最小，而后面的所有元素構成減序子集，這樣需要先將第1個元素換到最后，然后反轉后面的所有元素。交換次數為1+(n-1)/2，復雜度為O(n)。這樣平均復雜度即為O(n/2)。
//STL的生成方法
bool my_next_permutation(int * const begin, int * const end)
{
int *p1 , *p2;
for(p1 = end - 1; p1!= begin; p1--)//找到序列中從后往前第一個元素1小于元素2的一對
{
if(*(p1-1)< *(p1))
break;
}
if(p1==begin)//這種情況下序列已經完全逆序
return false;
p1--;//使p1指向小的那個數
for(p2 = p1 + 1; p2 != end; p2++)//尋找p1后面比p1小但是最大的那個數
//，這里利用了后面序列降序的性質
{
if(*p2 < *p1)
break;
}
p2--;//p2指向后面比p1大但是最小的那個
iter_swap(p1,p2);//交換p1，p2指向的元素
reverse(p1+1,end);//注意是到end 反向而非p2
return true;
}
請這樣調用
view plaincopy to clipboardprint?
do
{
for(int i = 0; i < MAX; i++)
{
cout << d[i] << " ";
}
cout << endl;
}while(my_next_permutation(d,d+MAX));
do
{
for(int i = 0; i < MAX; i++)
{
cout << d[i] << " ";
}
cout << endl;
}while(my_next_permutation(d,d+MAX));
部分內容引用：
http://blog.csdn.net/heartnheart/archive/2010/10/20/5953150.aspx
posted on 2011-03-08 11:29
Cunch 閱讀(610)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm