怎样输出可重集的全排列

#返回上一级

@Author: 张海拔

@Update: 2014-02-03

@Link: http://www.cnblogs.com/zhanghaiba/p/3533614.html

permutation1()可以输出[1, n]的全排列，通过实现这个函数回顾了一下回溯法。

比求n的全排列还基础的回溯法典型问题是：“怎样输出二叉树的所有路径（按字典序）？ link(public)”

permutation2()可以输出不可重集的全排列，主要是为了引出下一个函数。

permutation()可以输出可重复集合的全排列，功能完整。

三个函数均是独立可复用的，由于这个算法效率是指数级的，所以保存路径的path数组和vis标记数组可以放在递归函数中，同时设为static。

  1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-25
  4  *File: full_permutation.c
  5  *
  6  *a demo shows how to print full permutaion of [1,n] and Repeatable Set(a sorted string)
  7  */
  8 
  9 #include <stdio.h>
 10 #include <string.h>
 11 #define LEN 128
 12 
 13 //show permutation of [1, n]
 14 void permutation1(int step, int n);
 15 
 16 //guarantee sorted string and have not repeating characters
 17 void permutation2(int step, char *sorted_string, int string_len);
 18 
 19 //guarantee sorted string
 20 void permutation(int step, char *sorted_string, int string_len);
 21 
 22 int main(void)
 23 {
 24     int n;
 25     char str[LEN];
 26 
 27     scanf("%d", &n);
 28     permutation1(0, n);
 29     scanf("%s", str);
 30     permutation2(0, str, strlen(str));
 31     scanf("%s", str);
 32     permutation(0, str, strlen(str));
 33     return 0;
 34 }
 35 
 36 void permutation1(int step, int n)
 37 {
 38     static int path[LEN];
 39     static int vis[LEN];
 40     int i;
 41 
 42     if (step == n) {
 43         for (i = 0; i < n; ++i)
 44             printf(i == n-1 ? "%d
" : "%d", path[i]);
 45         return;
 46     }
 47     for (i = 0; i < n; ++i) {
 48         if (!vis[i]) {
 49             path[step] = i+1;
 50             vis[i] = 1;
 51             permutation1(step+1, n);
 52             vis[i] = 0;
 53         }
 54     }
 55 }
 56 
 57 void permutation2(int step, char *s, int n)
 58 {
 59     static char path[LEN];
 60     static int vis[LEN];
 61     char *p;
 62 
 63     if (step == n) {
 64         path[n] = '';
 65         printf("%s
", path);
 66         return;
 67     }
 68     for (p = s; *p; ++p) {
 69         if (!vis[*p]) {
 70             path[step] = *p;
 71             vis[*p] = 1;
 72             permutation2(step+1, s, n);
 73             vis[*p] = 0;
 74         }
 75     }
 76 }
 77 
 78 void permutation(int step, char *s, int n)
 79 {
 80     static char path[LEN];
 81     char *p;
 82     int i, cnt1, cnt2;
 83 
 84     if (step == n) {
 85         path[n] = '';
 86         printf("%s
", path);
 87         return;
 88     }
 89     for (p = s; *p; ++p) {
 90         if ( p == s || *p != *(p-1) ) { //for each repeatless character
 91             for (cnt1 = i = 0; i < step; ++i)
 92                 if (*p == path[i])
 93                     cnt1++; //count *p in path
 94             for (cnt2 = i = 0; i < n; ++i)
 95                 if (*p == s[i])
 96                     cnt2++; //count *p in source string
 97             if (cnt1 < cnt2) {
 98                 path[step] = *p;
 99                 permutation(step+1, s, n);
100             }
101         }
102     }
103 }