按字典顺序打印具有给定字符的所有可能字符串-解网

问：

问题描述：

他递给你一根绳子，问你是否能用它的字符说出尽可能多的不同单词。

很高兴尝试一下，你开始工作了。这感觉有点像解开一个谜题，并找到排列字母的新方法。每个安排都揭示了一个新的和有趣的词。你急切地投入到任务中，准备发现所有不同的单词你可以用这些给定的字母进行创作。

输入约束：1 <= n <= 8

输入：唯一的输入行有一个长度为的字符串。每个字符都介于“a-z”之间。n

输出：首先打印一个整数：字符串的数量。然后按字母顺序打印行：字符串。kk

这是我的代码，想问一下如何修改以按字母顺序获得所需的输出。时间限制为 1 秒。

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

void permutations(char array[], short length, short left)
{
    if (left == length)
    {
        //swap(&array[left - 1], &array[i]);
        printf("%s", array);
    }
    else
    {
        for (int i = left; i <= length; i++)
        {
            int is_duplicate = 0;
            for (int j = left; j < i; j++)
            {
                if (array[j] == array[i])
                {
                    is_duplicate = 1;
                    break;
                }
            }
            if (!is_duplicate)
            {
                swap(&array[left], &array[i]);
                permutations(array, length, left + 1);
                swap(&array[left], &array[i]);
            }
        }
    }
}

void main(void)
{
    char input[10] = "";
    fgets(input, 9, stdin);
    short str_len = strlen(input);
    //printf("%hd", str_len);
    quicksort(input, str_len - 1);
    //fputs(input, stdout);
    permutations(input, str_len - 2, 0);
    /*quicksort(input, str_len);*/
}

C 字符串算法排序

Knuth 的“算法 L”（词典排列生成）将负责对最初排序的字符串内容进行置换。在输出任何字符串之前，您还需要输出字符串的数量。您可以通过将长度的阶乘除以每个字母的重复计数的阶乘来做到这一点。例如，对于长度为 6 且字母重复计数为 2、1、3 的字符串（例如“aabccc”），字符串数将为 6！/ (2! * 1! * 3!)= 720 / （2 * 1 * 6） = 60。

0赞 Neil 10/10/2023

lg_2(8)*26=78位很容易融入完美的哈希值;我认为这是故意的。

答：

0赞 Ian Abbott 10/10/2023 #1

以下内容基于 Knuth 的“算法 L”，摘自“计算机编程的艺术”，第 4 卷，第 2 分册。请参阅 Muktal Gupta 的博客文章 Understanding Algorithm L 了解其工作原理。

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

#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 Algorithm 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 Algorithm L (Lexicographic permutation algorithm). */
        do
        {
            /* L1. [Visit.] */
            puts(input);
        }
        while (permute(input, len)); /* Steps L2. to L4. */
    }
    return 0;
}

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

Printing all possible strings with given characters in dictionary order

评论

评论