全排列问题的递归解法

KaQqi

思路有两个，一个是递归，一个是栈。两者的本质都是深度优先搜索。。

直接上代码。
第一题 p1199
http://ybt.ssoier.cn:8088/problem_show.php?pid=1199

[C++] 纯文本查看 复制代码

#include <stdio.h>
#include <string.h>

int longs;
char s[27];
char solution[27];

void Output()
{
	for(int i = 0;i<longs;i++)
	{
		printf("%c",solution[i]);
	}
	printf("\n");
}

bool not_used(char x)
{
	for(int i = 0;i<=longs;i++)
	{
		if(x == solution[i])
		{
			return 0;
		}
	}
	return 1;//没被用过 
}

int Go(int count)
{
	if(count == longs)
	{
		Output();
		solution[count] = 0;
		return 0;
	}
	for(int i = 0;i<longs;i++)
	{
		if(not_used(s[i]))
		{
			solution[count] = s[i];
			Go(count+1);
			solution[count] = 0;
		}
	}
}

int main()
{
	
	scanf("%s",&s);
	longs = strlen(s);

//	printf("%c\n",s[1]);
	Go(0);
	return 0;
}

第二题 p1706
https://www.luogu.org/problemnew/show/P1706

[C++] 纯文本查看 复制代码

#include <stdio.h>

int n;
char solution[10];

void Output()
{
	for(int i = 0;i<n;i++)
	{
		printf("%5d",solution[i]);
	}
	printf("\n");
}

bool not_used(int x)
{
	for(int i = 0;i<=n;i++)
	{
		if(x == solution[i])
		{
			return 0;
		}
	}
	return 1;//没被用过 
}

int Go(int count)
{
	if(count == n)
	{
		Output();
		solution[count] = 0;
		return 0;
	}
	for(int i = 1;i<=n;i++)
	{
		if(not_used(i))
		{
			solution[count] = i;
			Go(count+1);
			solution[count] = 0;
		}
	}
}

int main()
{
	scanf("%d",&n);
	Go(0);
	return 0;
}

zjgt

想想是不是可以优化呢，比如可以用一个数组来标记对应的数字或字母是否已使用，这样就不用再遍历一遍数组来判断是否已使用

KaQqi

zjgt 发表于 2019-4-15 14:11
想想是不是可以优化呢，比如可以用一个数组来标记对应的数字或字母是否已使用，这样就不用再遍历一遍数组来 ...

是的，可以打静态表来优化