## STL經典算法集錦<六>之排列（next_permutation/prev_permutation） 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; } } } ~~~