如何用非递归的算法来求解一个"全排列"

starwing83

很奇怪，为什么没有一个人对我贴的网址感兴趣呢……那我直接贴代码好了：

1. #include <stdio.h>
   
2. static void cswap(char *a, char *b) {
   
3.     char tmp = *a;
   
4.     *a = *b;
   
5.     *b = tmp;
   
6. }
   
7. static void creverse(char *begin, char *end) {
   
8.     while (begin < end)
   
9.         cswap(begin++, --end);
   
10. }
    
11. static char *csort(char *s) {
    
12.     char *i = s;
    
13.     for (; *i != '\0'; ++i) {
    
14.         char tmp = *i, *j = i, *cur;
    
15.         while (s < (cur = j--) && !(*j < tmp))
    
16.             *cur = *j;
    
17.         *cur = tmp;
    
18.     }
    
19.     return i;
    
20. }
    
21. static int next_permutation(char *begin, char *end) {
    
22.     char *i = end-1;
    
23.     while (begin < i) {
    
24.         char *cur = i--;
    
25.         if (*i < *cur) {
    
26.             char *j = end;
    
27.             while (!(*i < *--j))
    
28.                 ;
    
29.             cswap(i, j);
    
30.             creverse(cur, end);
    
31.             return 1;
    
32.         }
    
33.     }
    
34.     /*creverse(begin, end);*/
    
35.     return 0;
    
36. }
    
37. int main(void)
    
38. {
    
39.     char buf[101];
    
40.     while (gets(buf) != NULL) {
    
41.         char *bufend = csort(buf);
    
42.         do {
    
43.             printf("%s\n", buf);
    
44.         } while (next_permutation(buf, bufend));
    
45.     }
    
46.     return 0;
    
47. }

复制代码

本科僧

void permutation(char a[], int m, int n)
  {
      int i;
      char t;
      if (m<n-1) {
          permutation(a, m+1, n);
          for (i=m+1;i<n;i++) {
  
              t=a[m]; a[m]=a[i]; a[i]=t;
              permutation(a, m+1, n);
              t=a[m]; a[m]=a[i]; a[i]=t;
          }
      } else
          {
              printf("%s\n", a);
          }
  }

captivated

晕. 于是我又来mark了