生成上/下一个排列

生成下一个排列

我们从排列的后面找到第一个递减的位置$e$&＃xff0c;说明$e$之前的排列均已经排列完了&＃xff0c;我们把$e$位置上的元素与$e$之后第一个大于它的元素交换位置&＃xff0c;最后将$e$之后的元素按照升序排列即可。

生成上一个排列

我们从排列的后面找到第一个递增的位置$e$&＃xff0c;说明$e$之前的排列是第一个排列&＃xff0c;我们把$e$位置上的元素与$e$之后第一个小于它的元素交换位置&＃xff0c;最后将$e$之后的元素按照降序排列即可。

代码

生成上一个排列。

#include using namespace std;#define FR freopen("in.txt","r",stdin)typedef long long ll;int arr[25];
int n;bool solve()
{int e &＃61; n-1;for(; e>&＃61;0; e--){if(arr[e] > arr[e &＃43; 1]){break;}}if(e &＃61;&＃61; 0){return false;}int i &＃61; n;for(;i>e;i--){if(arr[i] < arr[e]){break;}}swap(arr[e],arr[i]);sort(arr&＃43;e&＃43;1,arr&＃43;1&＃43;n,greater<int>());return true;
}int main()
{arr[0] &＃61; INT_MAX;cin >> n;for(int i &＃61; 1; i<&＃61;n; i&＃43;&＃43;)cin >> arr[i];if(solve())copy(arr&＃43;1,arr&＃43;n&＃43;1,ostream_iterator<int>(cout," "));else cout << "ERROR";return 0;
}