STL經典算法集錦之排列（next_permutation/prev_permutation）

來自：CSDN博客推薦文章 | 時間：2012-05-07 14:54:09

原文鏈接： http://blog.csdn.net/xinhanggebuguake/article/details/7542542

相關主題： 1100008311010017

STL中涉及到數組的排列的有兩個函數，即next_permutation/prev_permutation，分別用于求上一個以及下一個排列。兩函數的算法使用的原理大體相同。以next_permutation為例，列出算法并解釋。

算法：

首先，從最為段開始往前尋找兩個相鄰的元素，令第一個元素索引為endi第二個元素索引為endii，且滿足array[endi]<array[endii]。然后，再從最尾端開始向前檢測，找到第一個大于array[endi]的元素，令其為索引j。將元素array[endi],array[j]對調，然后將endii之后的所有元素顛倒排列。即求的下一個排列。

解釋：

一、如果數組k以后的是一個遞減序列，則僅依靠調換k以后的元素不可能完成任務，所以必須找到滿足k>k+1的元素，即保證k以后的序列不遞減。

二、滿足一之后，那么下一個序列的第k位一定是從后面找到剛好比a[k]大的一個比a[k]大的一個數打頭的（為了保證剛好大于，又k+1之后的元素遞減，所以從數組尾開始找到第一個比a[k]大的元素即可滿足要求）。將這個數的索引記為j。

三、將a[j]與a[k]對調。此時，j后面的元素是降序的。所以需要把j后面的逆轉一下，從降序到升序，如此就得到了恰好比之前序列大一號的序列。

代碼：next_permutation

bool nextPermutation(int array[],int len) {int endi=len-1;int endii;if(len==1)return false;while(true){endii=endi;endi--;if(array[endi]<array[endii])// 如果前一個元素小于后一個元素{int j=len;while(array[--j]<array[endi]);// 由尾端往前找，直到遇上比array[endi]大的元素swap(array[j],array[endi]); // 交換找到的元素reverse(array+endii,array+len-1);// 將 endii 之后的元素全部逆向重排return true;}if(endi==0)//排列已至最大，無下一個排列{reverse(array,array+len-1);return false;}} } 代碼：prev_permutation

bool prevPermutation(int array[],int len) {int endi=len-1;int endii;if(len==1)return false;while(true){endii=endi;endi--;if(array[endi]>array[endii])// 如果前一個元素大于后一個元素{int j=len;while(array[--j]>array[endi]);// 由尾端往前找，直到遇上比array[endi]小的元素swap(array[j],array[endi]); // 交換找到的元素reverse(array+endii,array+len-1);// 將 endii 之后的元素全部逆向重排return true;}if(endi==0)//排列已至最小，無上一個排列{reverse(array,array+len-1);return false;}} }

總結

以上是生活随笔為你收集整理的STL经典算法集锦之排列（next_permutation/prev_permutation的全部內容，希望文章能夠幫你解決所遇到的問題。

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