问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1731思路:
求全排列，这个问题本身挺简单，不过题目要求: a. 不能重复；b. 有序输出
记得曾经做过这题，当时偷懒用STL过的(真要自己写，估计当时也不会(*^__^*) 嘻嘻……)
现在，决心弃用C++来做题，好好锻炼基本功，所以就硬着头皮自己慢慢写
好在前段时间对于搜索题有了一定的积累，否则相信自己肯定还是不知道怎么写的
找个例子，画出递归调用树，对于理解有很大帮助
纯C递归实现如下:
代码:
1 /* 364K 454MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 201
6 char str[MAX_LEN];
7 int len;
8
9 int
10 compare(const void *arg1, const void *arg2) /* for qsort */
11 {
12 return *((char *)arg1) - *((char *)arg2);
13 }
14
15 void
16 swap(char *seq, int i, int j) /* exchange */
17 {
18 char tmp = seq[i];
19 seq[i] = seq[j];
20 seq[j] = tmp;
21 }
22
23 void
24 perm(char *seq, int begin, int end)
25 {
26 int i, j, tmp;
27 char pre=0;
28 if(begin >= end) {
29 printf("%s\n", seq);
30 return;
31 }
32 for(i=begin; i<=end; i++) {
33 if(i>begin && seq[i]==seq[begin]) /* avoid duplicates */
34 continue;
35 if(pre == seq[i]) /* avoid duplicate */
36 continue;
37 /* in order to keep the alphabetical order */
38 tmp = seq[i];
39 for(j=i; j>begin; j--)
40 seq[j] = seq[j-1];
41 seq[begin] = tmp;
42 perm(seq, begin+1, end);
43 tmp = seq[begin];
44 for(j=begin; j<i; j++)
45 seq[j] = seq[j+1];
46 seq[i] = tmp;
47 /*
48 swap(seq, begin, i);
49 perm(seq, begin+1, end);
50 swap(seq, begin, i);
51 */
52 pre = seq[i];
53 }
54 }
55
56 int
57 main(int argc, char **argv)
58 {
59 while(scanf("%s", str) != EOF) {
60 len = strlen(str);
61 qsort(str, len, sizeof(char), compare);
62 perm(str, 0, len-1);
63 }
64 }