C++标准库中next_permutation和pre_permutation实现原理

水深无声 2022-04-13 09:23 139阅读 0赞

`原文链接：https://blog.csdn.net/yang20141109/article/details/51333417`

`标准库中next_permutation函数：找当前序列中元素排列的下一个排列，按照字典顺序进行排列。比如说数组排列"123"，那么它的下一个排列为"132"，并且返回true。如果当前序列没有下一个排列，我们返回false，且把当前排列置为最小的排列，比如说：排列"321"，因为该排列已经是最大的排列，所以它没有下一个排列。我们把该排列置为"123"，并且返回false。 标准库实现两个重载版本的next_permutation。第一个函数接受两个参数，并且返回一个bool值，第二个函数接受三个参数，也返回一个bool值。`

1.  bool next\_permutation(\_BidIt \_First, \_BidIt \_Last);//第一个参数指数组的开始位置的迭代器，第二个参数指数组结束位置的后一个位置的迭代器。
2.  bool next\_permutation(\_BidIt \_First, \_BidIt \_Last, \_Pr \_Pred);//前两个参数和第一个函数中参数表达的意思相同，第三个参数指数组中的元素按照何种序列进行比较。

next\_permutation函数的实现原理：我们把数组分割成三个划分，在第一个划分中的所有元素都不需要改变，第二个划分只有一个元素，并且该元素需要和第三个划分中的某个元素进行交换。在第三个划分中，所有元素都需要逆序处理。如图所示：

![Center][]

重点是我们如何把序列分割成三个划分。首先找到第三个划分和第二个划分的分界线。因为第三个划分按照由右向左按非降序排列，所以它们的分界线是第一对不满足非降序排列的元素中间的位置。第二个划分只有一个元素。剩余的元素自然就成为第一个划分。

把序列分割以后：我们需要对分割以后的划分进行操作。首先，在第三个划分中，找到第一个大于第二个划分中的元素的位置。比如上图中，在\{5,3,1,0\}中找到第一个大于\{2\}的元素的位置，最后找到的是元素3的位置。把2和3进行交换。然后把交换以后的第三个划分逆序。

![Center 1][]

![Center 2][]

代码实现如下：直接对序列进行排序：

bool nextPermutation(vector<int> &nums)
    {
    	int size = nums.size();
    	for (int i = size - 1; i > 0; --i)
    	{
    		//找到第二个划分与第一个划分的分界线
    		if (nums[i] > nums[i - 1])
    		{
    			int val = nums[i - 1];
    			int j = size - 1;
    			//找到第一大于val值的位置
    			for (; j >= i; --j)
    			{
    				if (nums[j] > val)
    					break;
    			}
    			//交换val值和第一个大于val的值
    			swap(nums[i - 1], nums[j]);
    			int l = i;
    			int r = size - 1;
    			//逆序处理
    			while (l < r)
    			{
    				swap(nums[l], nums[r]);
    				l++;
    				r--;
    			}
    			return true;
    		}
    	}
    	int start = 0;
    	int last = size - 1;
    	while (start < last)
    	{
    		swap(nums[start], nums[last]);
    		start++;
    		last--;
    	}
    	return false;
    }

标准库中还有prev\_permutation函数，找到当前序列的前一个序列，比如说序列"132"，返回的是"123"。实现代码如下：

bool prePermutation(vector<int> &nums)
    {
    	int size = nums.size();
    	for (int i = size - 1; i > 0; --i)
    	{
    		if (nums[i] < nums[i - 1])
    		{
    			int val = nums[i - 1];
    			int j = size - 1;
    			for (; j >= i; --j)
    			{
    				if (nums[j] < val)
    					break;
    			}
    			swap(nums[i - 1], nums[j]);
    			int l = i;
    			int r = size - 1;
    			while (l < r)
    			{
    				swap(nums[l], nums[r]);
    				l++;
    				r--;
    			}
    			return true;
    		}
    	}
    	int start = 0;
    	int last = size - 1;
    	while (start < last)
    	{
    		swap(nums[start], nums[last]);
    		start++;
    		last--;
    	}
    	return false;
    }

[Center]: /images/20220413/a0a158e8cc4340fdbda94ffc1dda5f5d.png
[Center 1]: /images/20220413/859652e7bdf947aa89ee840fcddb896e.png
[Center 2]: /images/20220413/f1039e9bd8a94abd8dcae1f7c1f9f45f.png