Problem

6 /6


所有排列

Theory Click to read/hide

长度为 n 的排列是没有重复数字 1、2、...、n 的有序集合。例如,[3, 1, 2] 和 [5, 4, 3, 2, 1] 是排列,但 [1, 2, 1, 3] 和 [1, 2, 4] 不是。

如果任务简化为需要遍历所有长度为 n 的排列,那么您可以使用 C++ 中一种方便的机制,称为“next_permutation”。

您可以在 文档中阅读更多相关信息,但重点是此函数会更改传递的数组以随后的字典顺序排列(通常是明确的和它的名字)。

要使用next_permutation,需要包含算法库(即在程序开头写#include

例子: 向量 arr; arr = { 1, 2, 3 }; // 数组是 [1, 2, 3] next_permutation(arr.begin(), arr.end()); // 将整个数组传递给函数 // 数组现在是 [1, 3, 2] arr = { 2, 3, 1 }; // 数组是 [2, 3, 1] next_permutation(arr.begin(), arr.end()); // 将整个数组传递给函数 // 数组现在是 [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // 可以将函数应用于数组的一部分,但实际上很少需要这样做 // 数组现在是 [3, 2, 1]
在这种情况下,该函数有一个布尔返回值,如果生成了下一个排列则为真,如果没有下一个排列则为假(当字典顺序中的最大排列被传递给函数时的情况)。
这使得在循环中使用该函数成为可能,这将允许我们一次迭代所有排列。由于 0 索引,在实践中使用从 0 到 n - 1 的数字排列通常更方便,尽管排列形式上包含从 1 到 n 的数字。但幸运的是,这不会导致代码中出现额外的叠加层,因为next_permutation 函数适用于 0 索引排列(甚至是数组中的重复元素,但您可以自己找到更多信息)。

通常,迭代所有排列的代码如下所示:   国际; // 排列大小 矢量烫发(n); // perm 是“permutation”的缩写,即“排列” for (int i = 0; i < n; i++) perm[i] = i; // 初始化初始排列 0, 1, ..., n - 1 做 { // 在循环中我们处理当前排列 } while (next_permutation(perm.begin(), perm.end())); // 如果没有下一个排列,则结束循环

此代码在 O(n! * f(n)) 中运行,其中 f(n) 是您处理一个特定排列所花费的时间。

Problem

给你一个自然数n。按字典顺序打印所有大小为 n 的排列。

输入:
第一行包含一个自然数 n (1 <= n <= 7)。

输出:
按字典顺序按升序打印所有排列。每个都在一个单独的行上。排列中的数字必须用空格分隔。

示例:
  <正文>
输入 输出
3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1