LG#P1706. 全排列问题

全排列问题

P1706 全排列问题

题目描述

\hspace{15pt}给定一个整数 nn,请按字典序输出由 1∼n1 \sim n 组成的全部排列。要求同一个排列中任何数字都不重复出现。

∙ \hspace{15pt}\bullet\,排列:长度为 nn 的排列是由 1∼n1 \sim n 这 nn 个整数按任意顺序组成的序列,其中每个整数恰好出现一次。例如 {2,3,1}\{2,3,1\} 是一个长度为 33 的排列,而 {1,2,2}\{1,2,2\} 不是排列。

∙ \hspace{15pt}\bullet\,字典序:从两个序列的第一个元素开始逐个比较,直到找到第一个不同的位置,通过比较这个位置元素的大小得出两个序列的大小,称为字典序比较。

输入格式

\hspace{15pt}输入一行一个整数 n(1≦n≦9)n \left(1 \leqq n \leqq 9\right) 代表排列的长度。

输出格式

\hspace{15pt}共输出 n!n! 行,每行一个长度为 nn 的排列,所有排列按字典序排列。

\hspace{15pt}每个数字占 55 个字符的位置,即在输出该数字之前补足空格,使其总宽度为 55。

测试样例

3
    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

样例 1 解释

\hspace{15pt}1∼31 \sim 3 的全排列共有 3!=63! = 6 个。按字典序比较时先看第一个数字,因此以 11 开头的排列全部排在以 22 开头的排列之前,以 22 开头的又全部排在以 33 开头的之前;第一个数字相同时再比较第二个数字,依此类推。

\hspace{15pt}例如 {1,3,2}\{1,3,2\} 与 {2,1,3}\{2,1,3\} 的第一个数字分别是 11 和 22,所以 {1,3,2}\{1,3,2\} 排在前面。

1
    1

样例 2 解释

\hspace{15pt}长度为 11 的排列只有 {1}\{1\} 一个,注意输出时数字 11 之前有 44 个空格,使其宽度为 55。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦91 \leqq n \leqq 9。

\hspace{15pt}输出的行数为 n!n!,当 n=9n = 9 时共有 9!=3.6288×1059! = 3.6288 \times 10^5 行,建议使用较快的输出方式。