博客

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);
}