今天看到 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++;
		}
	}
}

结果如下

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