C++ 中的 std next_permutation 和

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

std::next_permutation

它用于将范围 [first, last) 中的元素重新排列为下一个字典序更大的排列。一个排列是 N! 元素可以采用的可能排列（其中 N 是范围内的元素数）。不同的排列可以根据它们在字典上相互比较的方式进行排序。代码的复杂度为 O(n*n!)，其中还包括打印所有排列。

语法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c++复制代码模板
bool next_permutation（首先是
双向
迭代器， 最后是 双向迭代器 ）； 参数：
first, last : 初始的双向迭代器
和序列的最终位置。范围
used 是 [first, last)，其中包含所有元素 
在 first 和 last 之间，包括指向的元素 
by first 但不是 last 指向的元素。

返回值：
true ： 如果函数可以重新排列
对象作为字典序更大的排列。
否则，该函数返回 false 以指示 
安排不大于以前， 
但可能是最低的（按升序排序）。

应用： next_permutation 是为给定的值数组找到下一个字典序更大的值。

例子：

1
2
3
4
5
c++复制代码输入：1 2 3 的下一个排列是 
输出：1 3 2

输入：4 6 8 的下一个排列是 
输出：4 8 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c++复制代码#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	int arr[] = { 1, 2, 3 };

	sort(arr, arr + 3);

	cout << "3！3个元素的可能排列:\n";
	do {
		cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
	} while (next_permutation(arr, arr + 3));

	cout << "循环后: " << arr[0] << ' '
		<< arr[1] << ' ' << arr[2] << '\n';

	return 0;
}

输出：

1
2
3
4
5
6
7
8
c++复制代码3！3个元素的可能排列：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
循环后：1 2 3

std::prev_permutation

它用于将范围 [first, last) 中的元素重新排列为前一个按字典顺序排列的排列。一个排列是 N! 元素可以采用的可能排列（其中 N 是范围内的元素数）。不同的排列可以根据它们在字典上相互比较的方式进行排序。

语法 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c++复制代码模板
bool prev_permutation（首先是
双向
迭代器， 最后是 双向迭代器 ）； 参数：
first, last : 初始的双向迭代器
和序列的最终位置。范围
使用的是 [first, last)，其中包含所有
first 和 last 之间的元素，包括 
first 指向的元素但不是元素
最后指出。

返回值：
true ： 如果函数可以重新排列
对象作为字典序较小的排列。
否则，该函数返回 false 以指示 
安排不低于以前， 
但最大的可能（按降序排序）。

应用： prev_permutation 是为给定的值数组找到以前的字典序较小的值。

例子：

1
2
3
4
5
c++复制代码输入：3 2 1的prev排列是 
输出：3 1 2 

输入：8 6 4 的上一个排列是 
输出：8 4 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
c++复制代码#include <algorithm>

#include <iostream>
using namespace std;
int main()
{
	int arr[] = { 1, 2, 3 };

	sort(arr, arr + 3);
	reverse(arr, arr + 3);

	cout << "3！3个元素的可能排列:\n";
	do {
		cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
	} while (prev_permutation(arr, arr + 3));

	cout << "循环后: " << arr[0] << ' ' << arr[1]
		<< ' ' << arr[2] << '\n';

	return 0;
}

输出：

1
2
3
4
5
6
7
8
c++复制代码3！3个元素的可能排列：
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
循环后：3 2 1

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%