重复打印排序排列

Question

我想按字典顺序重复打印所有排列的字符串。我写这篇文章的代码：

char *input; 

void swap(char *x, char *y); 

void permute(char *str); 

int factorial(int n); 

void swapSort(char array[], int left, int right); 

void quick_sort(char *array, int left, int right); 

//void permute(char *str, char *p_ch, int length); 

int main() { 
    input = malloc(8 + 1 * sizeof(char)); 
    fgets(input, 9, stdin); 
    int n = strlen(input); 
    if (input[n - 1] == '\n') { 
     n--; 
     input[n] = '\0'; 
    } 
    printf("Length of string: %d\n", n); 
    printf("Input string: \"%s\"\n", input); 
    quick_sort(input, 0, n); 
    printf("sorted string: \"%s\"\n", input); 
    printf("Number of permutations: %d\n", factorial(n)); 
    permute(input); 
    //free(input); 
    return 0; 
} 

int factorial(int n) { 
    if (n == 1) return 1; 
    return n * factorial(n - 1); 

} 


int compare(const void *a, const void *b) { 
    return (*(char *) a - *(char *) b); 
} 


void permute(char *str) { 
    int strSize = strlen(str); 
    qsort(str, strSize, sizeof(char), compare); 

    int endIsNotReached = true; 
    int tmpSize; 
    while (endIsNotReached) { 

     printf("\"%s\"\n", str); 
     for (tmpSize = strSize - 2; tmpSize > -1 && str[tmpSize] >= str[tmpSize + 1]; tmpSize--) { 
      //do nothing 
     } 

     if (tmpSize > -1) { 
      int j = 1 + tmpSize; 
      for (int index = j; index < strSize && str[index]; index++) { 
       if (str[index] < str[j] && str[index] > str[tmpSize]) 
        j = index; 
      } 

      swap(&str[tmpSize], &str[j]); 

      qsort(str + tmpSize + 1, strSize - 1 - tmpSize, sizeof(char), compare); 
     } 
     else { 
      endIsNotReached = false; 
     } 
    }; 
} 
void quick_sort(char *array, int left, int right) { 
    if (left < right) { 
     int boundary = left; 
     for (int i = left + 1; i < right; i++) { 
      if (array[i] < array[left]) { 
       swapSort(array, i, ++boundary); 
      } 
     } 
     swapSort(array, left, boundary); 
     quick_sort(array, left, boundary); 
     quick_sort(array, boundary + 1, right); 
    } 

} 
void swapSort(char array[], int left, int right) { 
    char tmp = array[right]; 
    array[right] = array[left]; 

    array[left] = tmp; 
} 


void swap(char *left, char *right) { 
    char temp = *left; 
    *left = *right; 
    *right = temp; 
} 

但是当我要打印字符串“AAA”输出仅仅是“AAA”，但我想有输出，其中为“AAA”的三倍。 （另一例 - 输入 - “AAB” - 输出 - “AAB”， “AAB”， “ABA”， “ABA”， “BAA”， “BAA”）

Answer 1

即使OP可以”使用C++和它的标准库，我们可以看看std::next_permutation的一个可能的实现，并在C中转换它以利用它的字典顺序结果。

bool next_permutation(char *first, char *last) { 
    if (first == last) 
     return false; 
    char *i = last; 
    if (first == --i) 
     return false; 

    char *i1, 
     *i2; 

    while (true) { 
     i1 = i; 
     if (*--i < *i1) { 
      i2 = last - 1; 
      while (*i >= *i2) --i2; 
      swap(i, i2); 
      reverse(i1, last); 
      return true; 
     } 
     if (i == first) { 
      reverse(first, last); 
      return false; 
     } 
    } 
} 

void reverse(char *first, char *last) { 
    while ((first != last) && (first != --last)) { 
     swap(first, last); 
     ++first; 
    } 
} 

我想指出的是，虽然在OP的例子 “AAA” 有望被repeted 3次，全部重复应该是6（或3！）：

一个一一个
一个一个一个
一个一个一个
一个一个一个
一个一个一个
一个一个一个

所以permute()看起来是这样的：

void permute(char *str, int length) { 
    static int count = 0; 
    int i, rep = 1; 

    // first sort the string 
    qsort(str, length, 1, compare); 

    // then calculate the repetitions 
    for (i = 1; i < length; ++i) { 
     if (str[i] == str[i - 1]) 
      ++rep; 
    } 

    int repetitions = factorial(rep); 

    do { 
     ++count;   
     printf("%5d: %s\n", count, str); 
    } while (count % repetitions || next_permutation(str, str + length)); 
} 

我稍微修改main()太：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 
// this is ^^^ for bool, but if if C99 is not an option: 
// typedef enum { false = 0, true = !false } bool; 


int factorial(int n); 
void swap(char *x, char *y); 
void reverse(char *first, char *last); // used by next_permutation 
bool next_permutation(char *first, char *last); 
void permute(char *str, int length); 

enum { WORD_MAX_SIZE = 16, ARRAY_SIZE }; 

int main(void) { 
    char input[ARRAY_SIZE]; 

    fgets(input, ARRAY_SIZE, stdin); 
    int n = strlen(input); 
    if (input[n-1] == '\n') { 
     --n; 
     input[n] = '\0';  
    } 

    printf("Length of string: %d\n", n); 
    printf("Input string: \"%s\"\n", input); 

    printf("Number of permutations: %d\n", factorial(n)); 
    permute(input, n); 

    return 0; 
} 

int factorial(int x) { 
    int f = x; 
    while (x > 1) { 
     f *= --x; 
    } 
    return f; 
} 

int compare(const void *a, const void *b) { 
    return (*(char *) a - *(char *) b); 
} 

void swap(char *left, char *right) { 
    char temp = *left; 
    *left = *right; 
    *right = temp; 
} 

例子：

Input string: "aba" 
Number of permutations: 6 
    1: aab 
    2: aab 
    3: aba 
    4: aba 
    5: baa 
    6: baa 

Input string: "baca" 
Number of permutations: 24 
    1: aabc 
    2: aabc 
    3: aacb 
    4: aacb 
    5: abac 
    6: abac 
    7: abca 
    8: abca 
    9: acab 
    10: acab 
    11: acba 
    12: acba 
    13: baac 
    14: baac 
    15: baca 
    16: baca 
    17: bcaa 
    18: bcaa 
    19: caab 
    20: caab 
    21: caba 
    22: caba 
    23: cbaa 
    24: cbaa