今天看到 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++; } } }
结果如下
但是至于怎么把这段递归等价的改写成循环,想了很是有一会儿,可惜暂时没有想出来
Pingback: 输出一个字符串的组合 | ZRJ
Pingback: 生成可重集的排列 | ZRJ