C++ 按字典顺序打印具有给定字符的所有可能字符串

以下是基于Knuth的《计算机编程的艺术》第四卷第二章中的算法L的内容.

在输出任何字符串之前，程序需要输出字符串的数量.count_permutations()函数用于计算将输出的字符串数.如果长度为n的字符串中的所有字符都不同，则数字只是n的阶乘.对于字符串中的每个不同字母，该数字需要除以该字母出现次数的阶乘.例如，如果字符串由1‘a’、2‘b和5’c组成，总长度为8，则字符串数将为8！/(1！×2！×5！)=40320/(1×2×120)=168.

#include <stdio.h>
#include <string.h>
//#include "quick_sort.h"
//#include "swap.h"
#include <stdlib.h>

void swap(char *a, char *b)
{
    char x = *a;
    *a = *b;
    *b = x;
}

int cmpchar(const void *a, const void *b)
{
    char av = *(const char *)a;
    char bv = *(const char *)b;
    return (av > bv) - (av < bv);
}

void quicksort(char *arr, size_t len)
{
    qsort(arr, len, sizeof *arr, cmpchar);
}

unsigned int factorial(unsigned int n)
{
    unsigned int fac = 1;
    unsigned int i;

    for (i = 2; i <= n; i++)
    {
        fac *= i;
    }
    return fac;
}

unsigned int count_permutations(const char *a, unsigned int n)
{
    unsigned int count = factorial(n);
    unsigned int i;
    unsigned int run;

    run = 0;
    for (i = 0; i < n; i++)
    {
        if (i == 0 || a[i] != a[i - 1])
        {
            count /= factorial(run);
            run = 0;
        }
        run++;
    }
    count /= factorial(run);
    return count;
}

/* Steps L2 to L4 of Knuth's 算法rithm L. */
int permute(char *a, int n)
{
    int j;
    int k;
    int l;

    if (n < 1)
    {
        n = 1;
    }
    /* L2. [Find j.] (N.B. reduce indices by 1 for C arrays.) */
    for (j = n - 1; j > 0 && a[j - 1] >= a[j]; j--)
        ;
    if (j == 0)
        return 0;
    /* L3. [Increase a_j.] (N.B. reduce indices by 1 for C arrays.) */
    for (l = n; a[j - 1] >= a[l - 1]; l--)
        ;
    swap(&a[j - 1], &a[l - 1]);
    /* L4. [Reverse a_(j+1) ... a_n.] (N.B. reduce indices by 1 for C arrays.) */
    for (k = j + 1, l = n; k < l; k++, l--)
    {
        swap(&a[k - 1], &a[l - 1]);
    }
    return 1;
}

int main(void)
{
    char input[10] = "";
    int len;

    if (fgets(input, 10, stdin) && input[0] != '\n')
    {
        len = strlen(input);
        /* Limit length. */
        if (len > 8)
        {
            len = 8;
        }
        /* Remove newline. */
        if (input[len - 1] == '\n')
        {
            len--;
        }
        input[len] = '\0';
        /* Initially sort in ascending order. */
        quicksort(input, len);
        /* Print number of permutations. */
        printf("%u\n", count_permutations(input, len));
        /* Use Knuth's 算法rithm L (Lexicographic permutation algorithm). */
        do
        {
            /* L1. [Visit.] */
            puts(input);
        }
        while (permute(input, len)); /* Steps L2. to L4. */
    }
    return 0;
}