打印带重复的排序排列

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] = '[=10=]';
    }
    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" 处输出三次。（再举个例子-input-"aab"-output-"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" 预计会重复 3 次，但所有重复都应为 6 次（或 3 次！）：

a₁a₂a₃
a₁a₃a₂
a₂a₁a₃
a₂a₃a₁
a₃a₁a₂
a₃a₂a₁

所以 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] = '[=12=]';       
    }

    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

打印带重复的排序排列

Print sorted permutations with repetitions

c

permutation