输出一个字符串的全排列

今天看到 http://blog.csdn.net/morewindo… 这里提出了一个问题

用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba

想了想(想了好久啊,好久没有碰数据结构和算法了),觉得可以 dfs,这样来搞:

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

#define MAX 1000

char str[MAX];
int len;
char tmp[MAX];
char used[MAX];

void arrange(int pos)
{
	if (pos >= len)
	{
		printf("%sn", tmp);
		return;
	}
	int i = 0;
	for (i=0; i<len; i++)
	{
		if ( ! used[i])
		{
			used[i] = 1;
			tmp[pos] = str[i];
			arrange(pos+1);
			used[i] = 0;
		}
	}
}

int main()
{
	scanf("%s", str);
	len = strlen(str);
	memset(used, 0, sizeof(used));
	memset(tmp, 0, sizeof(tmp));
	arrange(0);
	return 0;
}

结果如下:

但是问题是如果过滤掉重复的呢,最简单的一个想法是,用 stl 搞个 set,找到的结果先不打印出来,统统往 set 里面装,让 set 天然的帮我们过滤,最后用一个循环输出出来,但是,如果自己实现呢,回头看我们之前的代码,我们可以发现,在 dfs 的时候,字符在串中位置是有影响的,也就是说,对于上面的程序来说,abca 和 abac 是不一样的,但是,我们却希望,字符在串中的位置是无关紧要的,自然就想到,如果我们把相同的字符归成一群,这样就能解决问题,也就是说,我们需要把刚刚那两个串预处理一下,把他们都变成,一坨 a,然后一个 b,然后一个 c,于是得到下面的代码

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

#define MAX 1000

typedef struct _letter {
	char ch;
	int count;
} letter;

letter letters[MAX];
int letters_arr_size = 0;

char input[MAX];
int len;
char tmp[MAX];

void preprocess();
void dfs(int pos);

int main()
{
	scanf("%s", input);
	len = strlen(input);
	preprocess();
	dfs(0);
	return 0;
}

void preprocess()
{
	memset(letters, 0, sizeof(letters));
	int i, j, found=0;
	for (i=0; i<len; i++)
	{
		found = 0;
		for (j=0; j<letters_arr_size; j++)
		{
			if (input[i] == letters[j].ch)
			{
				letters[j].count++;
				found = 1;
				break;
			}
		}
		if ( ! found)
		{
			letters[letters_arr_size].ch = input[i];
			letters[letters_arr_size].count = 1;
			letters_arr_size++;
		}
	}
}

void dfs(int pos)
{
	if (pos >= len)
	{
		printf("%sn", tmp);
		return;
	}
	int i;
	for (i=0; i<letters_arr_size; i++)
	{
		if (letters[i].count > 0)
		{
			letters[i].count--;
			tmp[pos] = letters[i].ch;
			dfs(pos+1);
			letters[i].count++;
		}
	}
}

结果如下

但是至于怎么把这段递归等价的改写成循环,想了很是有一会儿,可惜暂时没有想出来

2 thoughts on “输出一个字符串的全排列

  1. Pingback: 输出一个字符串的组合 | ZRJ

  2. Pingback: 生成可重集的排列 | ZRJ

Leave a Reply

Your email address will not be published. Required fields are marked *