排列

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 #define MAXLINE 4096
  6 
  7 void next_permutation(char *str);                    //下一个排列
  8 void prev_permutation(char *str);                    //上一个排列
  9 void random_shuffle(char *begin,char *end);         //随机排列
 10 
 11 int main()
 12 {
 13     char str[MAXLINE];
 14     strncpy(str,"0123456789",MAXLINE);
 15 
 16     int i;
 17     for(i = 0;i < 10000;i++){
 18         next_permutation(str);
 19     }
 20     printf("%s\n",str);
 21     for(i = 0;i < 10000;i++){
 22         prev_permutation(str);
 23     }
 24     printf("%s\n",str);
 25 
 26     random_shuffle(str,str + strlen(str) - 1);
 27     printf("%s\n",str);
 28 
 29     return 0;
 30 }
 31 
 32 void swap(char *a,char *b)
 33 {
 34     char t = *a;
 35     *a = *b;
 36     *b = t;
 37 }
 38 
 39 //反转字符串
 40 void reverse(char *begin,char *end)
 41 {
 42     int i;
 43     for(i = 0;i <= (end - begin + 1) / 2;i++){
 44         swap(begin + i,end - i);
 45     }
 46 }
 47 
 48 void next_permutation(char *str)
 49 {
 50     int len = strlen(str);
 51     int i = len - 2;
 52 
 53     while(i >= 0 && str[i] >= str[i + 1]){
 54         i--;
 55     } 
 56     if(i == -1){
 57         return;
 58     }
 59     //i之后的字符串已达最大排列
 60     
 61     int j = len - 1;
 62     while(str[j] <= str[i]){
 63         j--;
 64     }
 65     //j为从后数第一个str[j]大于str[i]的位置
 66     
 67     swap(&str[i],&str[j]);
 68     reverse(str + i + 1,str + len - 1);
 69 }
 70 
 71 //正好相反
 72 void prev_permutation(char *str)
 73 {
 74     int len = strlen(str);
 75     int i = len - 2;
 76 
 77     while(i >= 0 && str[i] <= str[i + 1]){
 78         i--;
 79     }
 80     if(i == -1){
 81         return;
 82     }
 83 
 84     int j = len - 1;
 85     while(str[j] >= str[i]){
 86         j--;
 87     }
 88 
 89     swap(&str[i],&str[j]);
 90     reverse(str + i + 1,str + len - 1);
 91 }
 92 
 93 void random_shuffle(char *begin,char *end)
 94 {
 95     if(begin == end){
 96         return;
 97     }
 98 
 99     char *ptr;
100     for(ptr = begin + 1;ptr != end;ptr++){
101         swap(ptr,begin + rand() % (ptr - begin + 1));
102     }
103 }