时间戳

首页 > 解决方案 > 从通用字符串中获取可能的字谜的数量，需要一个快速的解决方案

c# - 从通用字符串中获取可能的字谜的数量，需要一个快速的解决方案

问题描述

我目前正在做一个任务，我需要编写一个小程序，该程序将采用通用字符串，并应输出可以从字符串生成多少个可能的字谜。作为输入的字符串最长可达 100 个字符，并且可以包括小写和大写，在这种情况下，小写和大写都被认为是不同的。输出应该只有多少种可能的组合，所以我不需要输出实际的字谜。最大时间限制是每个字符串 1 秒。

我尝试了许多不同的方法来做到这一点，但一个结论是，这应该可以使用某种数学算法来解决。

我尝试过的最新代码是这样的：

static void Main(string[] args)
{
    string line;
    while ((line = Console.ReadLine()) != null)
    {
        var uniqueStringArr = removeDuplicates(line);

        Console.WriteLine(countDistinctPermutations(new string(uniqueStringArr)));
    }
}

private static char[] removeDuplicates(string line)
{
    var list = line.ToList();

    return list.Distinct().ToArray();
}

static int MAX_CHAR = 100;

// Utility function to find factorial of n. 
static int factorial(int n)
{
    int fact = 1;
    for (int i = 2; i <= n; i++)
        fact = fact * i;

    return fact;
}

// Returns count of distinct permutations 
// of str. 
static int countDistinctPermutations(String str)
{
    int length = str.Length;

    int[] freq = new int[MAX_CHAR];

    // finding frequency of all the lower case 
    // alphabet and storing them in array of 
    // integer 
    for (int i = 0; i < length; i++)
        if (str[i] >= 'a')
            freq[str[i] - 'a']++;

    // finding factorial of number of appearances 
    // and multiplying them since they are 
    // repeating alphabets 
    int fact = 1;
    for (int i = 0; i < MAX_CHAR; i++)
        fact = fact * factorial(freq[i]);

    // finding factorial of size of string and 
    // dividing it by factorial found after 
    // multiplying 
    return factorial(length) / fact;
}

问题是这段代码没有为我所有的测试用例给出正确的答案。为我提供了以下示例数据：

输入字符串 | 可能的字谜数

在 | 2

磨难| 5040

abcdefghijklmnopqrstuvwxyz | 403291461126605635584000000

abcdefghijklmabcdefghijklm | 49229914688306352000000

abcdABCDabcd | 29937600

我的代码修复了前两个示例，但我得到了其他 3 个完全不同的数字。

有没有人可以帮助我解决这个问题，因为我的想法不多了？

/安德烈亚斯

标签： c#

解决方案

static BigInteger Factorial(long x)
{
    return x <= 1 ? 1 : x * Factorial(x-1);
}

private static BigInteger NumberOfDistinctPermutationOf(string str)
{
    BigInteger dividend = Factorial(str.Length);

    foreach (char chr in str)
    {
        dividend /= Factorial(str.Count(c => c == chr));
        str = str.Replace(chr.ToString(), string.Empty);
    }

    return dividend;
}

描述：

  • BigIntegerStruct：表示一个任意大的有符号整数。

  • Enumerable.Count 方法：返回一个数字，表示指定序列中有多少元素满足条件。

  • String.Replace(String, String)方法：返回一个新字符串，其中当前实例中出现的所有指定字符串都替换为另一个指定字符串。

  • GetNumberOfDistinctPermutation方法：将字符串长度的阶乘除以出现的次数的阶乘，char然后删除字符串char中每个出现的 , char。

推荐阅读