P1706 全排列问题
P1706 全排列问题
题目
题目描述
按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数n。
输出格式
由 1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个场宽。
输入输出样例
输入 #1复制
3
输出 #1复制
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
说明/提示
1≤n≤9。
解题思路
方法1：
对一个数组中的每个元素进行交换实现全排列
但是顺序不是按字典序，不能AC该题目
把数组后面还未摆放的数，到摆放到k(当前要排的位置)的位置上(交换)
不用使用额外的判断数组进行是否使用过的判断
#include <bits/stdc++.h> using namespace std; int nums[9] = {1,2,3,4,5,6,7,8,9}; int n; void f( int k ) { //n个数排列完成 //输出结果 if ( k==n ) { for( int i=0; i<n; i++ ) { printf( "%5d", nums[i] ); } cout << endl; return ; } //k为当前要排的位置 //从k开始后面的数都还没有排列 //从k开始遍历后面的数 //逐个排列(交换) for ( int i=k; i<n; i++ ) { //交换 int t = nums[i]; nums[i] = nums[k]; nums[k] = t; //递归 f( k+1 ); //恢复状态 t = nums[i]; nums[i] = nums[k]; nums[k] = t; } } int main() { cin >> n; f(0); }
方法2：
需要额外的数组进行判断数字是否使用过
该方法实现的全排列按照字典序
每次都重新遍历一次数组，查看那个数字未使用就放到当前要排列的位置，同时标记
#include <bits/stdc++.h> using namespace std; int nums[9] = {1,2,3,4,5,6,7,8,9}; int n; //判断标记数组 int flag[9] = {0,0,0,0,0,0,0,0,0}; //答案数组 int res[9] = {0,0,0,0,0,0,0,0,0}; void f2( int len ) { //排序完成输出 if ( len==n ) { for( int i=0; i<n; i++ ) { printf( "%5d", res[i] ); } cout << endl; return ; } //从头开始检查那些元素未使用 for ( int i=0; i<n; i++ ) { if ( flag[i]==1 ) { //使用过跳过 continue; } //未使用的排到该位置 res[len] = nums[i]; flag[i] = 1;//标记 f2( len+1 ); flag[i] = 0;//恢复 } } int main() { cin >> n; f2(0); }
