欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

全排列问题(可重复排列和不可重复排列)

程序员文章站 2022-03-22 19:06:51
...

全排列

1. 不可重复全排列

全排列问题一般要求按照字典顺序排列出来.

例如:

1 2 3     1 3 2

2 1 3     2 3 1

3 1 2     3 2 1

全排列问题一般尝试用递归的方式去做,用 for 循环来解决字典序的问题.

#include <cstdio>
using namespace std;
const int N=1024;
int vis[N];
int A[N];
void print_permutation(int n,int cur)
{
	if (cur==n)			//cur==n 表示已经得到一组排列,输出 
	{
		for (int i=0;i<n;i++)
			printf ("%d ",A[i]);
		printf ("\n");
		return ; 
	}
	for (int i=1;i<=n;i++)//for 循环中依次增大,保证了字典序
	{
		if (vis[i]==0)//当元素 i 没有出现,则加入当前 A 中 
		{
			A[cur++]=i;
			vis[i]=1;
			print_permutation(n,cur);
			cur--;		//注意恢复变量,这样在下一层的排列中,元素 i 可以被选中 
			vis[i]=0;
		}
	}
}
int main()
{
	int n;
	scanf ("%d",&n);
	print_permutation(n,0);
	return 0;
} 

2. 可重复全排列

相关标签: 全排列