枚舉所有排列的另一個方法是從字典序最小排列開始，不停調用“求下一個排列”的過 程。
全排列的個數A(N,N)=(N)(N-1)…*2*1=N!
下一個排列：通常按照升序順序（字典序）獲得下一個排列
stl

next_permutation找下一個排列的算法

如果一個數組arr[]中存在重復元素，next_permutation是否工作正常呢？

STL使用“!(*i < *j)”進行判斷大小，若相等則繼續尋找，這樣就會跳過重復的元素，進而跳過重復的全排列（如：1,2,2; 和1,2,2）。

返回值？

當返回為1時，表示找到了下一全排列；返回0時，表示無下一全排列。注意，如果從begin到end為降序，則表明全排列結束。

原理？

一個目的，不斷地找最接近這個排列的下個排列，直到全部降序為止

template<calss BidrectionalIterator> bool next_permutation(BidrectionalIterator first,BidrectionalIterator last) { if(first == lase) return false; /* 空區間 */ BidrectionalIterator i = first; ++i; if(i == last) return false; /* 只有一個元素 */ i = last; /* i指向尾端 */ --i; for(;;) { BidrectionalIterator ii = i; --i; /* 以上鎖定一組(兩個)相鄰元素 */ if(*i < *ii) /* 如果前一個元素小于后一個元素 */ { BidrectionalIterator j = last; /* 令j指向尾端 */ while(!(*i < *--j)); /* 由尾端往前找，直到遇到比*i大的元素 */ iter_swap(i,j); /* 交換i,j */ reverse(ii,last); /* 將ii之后的元素全部逆序重排 */ return true; } if(i == first) /* 進行至最前面了 */ { reverse(first,last); /* 全部逆序重排 */ return false; } } }

怎么用？

#include<cstdio> #include<algorithm> //包含next_permutation using namespace std; int main( ) { int n, p[10]; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &p[i]); sort(p, p+n); //排序，得到p的最小排列 do { for(int i = 0; i < n; i++){printf("%d ", p[i]); //輸出排列p}printf("\n"); } while(next_permutation(p, p+n)); //求下一個排列 return 0; }

do…while 循環是 while 循環的變體。在檢查while()條件是否為真之前，該循環首先會執行一次do{}之內的語句，然后在while()內檢查條件是否為真，如果條件為真的話，就會重復do…while這個循環,直至while()為假。

總結

以上是生活随笔為你收集整理的利用next_permutation解答全排列问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。