NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 27 题

1.（排列数）输入两个正整数 $n, m (1 \leq n \leq 20, 1 \leq m \leq n)$，在 $1\sim n$ 中任取 $m$ 个数，按字典序从小到大输出所有这样的排列。例如: 输入：3 2 输出：1 2 1 3 2 1 2 3 3 1 3 2

#include <iostream>
#include <cstring>
using namespace std;
const int	SIZE = 25;
bool		used[SIZE];
int		data[SIZE];
int		n, m, i, j, k;
bool		flag;
int main()
{
	cin >> n >> m;
	memset( used, false, sizeof(used) );
	for ( i = 1; i <= m; i++ )
	{
		data[i] = i;
		used[i] = true;
	}
	flag = true;
	while ( flag )
	{
		for ( i = 1; i <= m - 1; i++ )
			cout << data[i] << " ";
		cout << data[m] << endl;
		flag = ①;
		for ( i = m; i >= 1; i-- )
		{
			②;
			for ( j = data[i] + 1; j <= n; j++ )
				if ( !used[j] )
				{
					used[j] = true;
					data[i] = ③;
					flag	= true;
					break;
				}
			if ( flag )
			{
				for ( k = i + 1; k <= m; k++ )
					for ( j = 1; j <= ④; j++ )
						if ( !used[j] )
						{
							data[k] = j;
							used[j] = 

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

字典序排列生成：used 标记 + 递归回溯。填空：false、used[data[i]]=false、j、n、break。

标准字典序排列算法：选未使用的数递归，回溯时恢复 used 标记。

程序填空——排列生成

按字典序输出从1~n中选m个数的所有排列。

填空答案： (1) false — 初始设为false，找到下一个排列时设为true (2) used[data[i]]=false — 回溯，释放当前数字 (3) j — 当前位置填入j (4) n — 搜索范围1~n (5) break — 找到一个未使用的数字就停止

核心算法：从右向左找可以增大的位置，替换为更大的可用数字，后面的按升序填充。