代码之家 › 专栏 › 技术社区 › Adrian K

如何比较排列

string-comparison permutation c#

-1

Adrian K · 技术社区 · 7 年前

上下文

(我在codegolf.stackexchange.com上提出了这个问题,但他们说这是离题的,并在这里提出了建议)。

设计的核心是虚拟转子(Enigma中使用的物理转子的数字等价物),其中(简单地说)一个可见字母映射到一个秘密字母。

例如,如果给定转子上的可见字母是a-Z,那么我们可以这样描述秘密映射:

ABCDEFGHIJKLMNOPQRSTUVWXYZ - A-Z
EKMFLGDQVZNTOWYHXUSPAIBRCJ - Rotor I
AJDKSIRUXBLHWTMCQGZNPYFVOE - Rotor II
BDFHJLCPRTXVZNYEIWGAKMUSQO - Rotor III

这个问题

我想做的是生成一组潜在的新转子映射,并以某种方式评估它们的相似性,例如:

BDFHJLCPRTXVZNYEIWGAKMUSQO - Rotor III
ZGFHJLCPRXTVDNYEIWBAMUKOQS - Random Rotor A
VZBRGITYUPSDNHLXAWMJQOFECK - Random Rotor B
NYEIWGAKMUSQOBDFHJLCPRTXVZ - Random Rotor C

与转子III相比,随机转子A不同,但B的变化更明显。转子C看起来与转子III有很大不同,但事实并非如此,它只是将转子III切成两半,第二部分放在第一部分的前面。

仅供参考,我会使用C来构建这个,但很乐意接受我可以实现的任何像样的逻辑。

使现代化

比较不必非常精确。字符串的长度将超过26-将在100+左右变化,尽管所有字符串的长度将相同。排列的数量也会有所不同,但可能是100多个。

2 回复 | 直到 7 年前

Rufus L 7 年前

一种选择是简单地编写自己的方法来确定两个字符串之间的相似性。

private static int GetSimilarity1(string first, string second)
{
    if (first == null) return second == null ? 100 : 0;

    // Set similarity to the percentage of characters in the same position
    var matches = first.Count(chr => first.IndexOf(chr) == second.IndexOf(chr));
    return (int)(matches / (decimal)first.Length * 100);
}

第二种方法是取第二个字符串中每个字符与第一个字符串中的索引的距离,然后除以它与索引的最大距离(最坏情况)。这将导致精确匹配的值较低(0),或者距离越远,值越高。然后,将该数字从1中减去(从“坏”百分比(精确匹配为0)转换为“好”百分比(精确匹配为1))并乘以100,将其转换为一个百分比。然后将该数字添加到运行总数中。

最后,将总数除以字符数,得到最终的“相似性”百分比。

private static int GetSimilarity2(string first, string second)
{
    if (first == null) return second == null ? 100 : 0;

    int distance = 0;

    for(int i = 0; i < first.Length; i++)
    {
        var thisDist = Math.Abs(second.IndexOf(first[i]) - i);
        var worstDist = Math.Max(first.Length - i - 1, i);
        distance += (int)((1 - thisDist / (decimal) worstDist) * 100);
    }

    return distance / first.Length;
}

为了测试这些方法,我使用了以下代码:

private static void Main()
{
    var rotorIII = "BDFHJLCPRTXVZNYEIWGAKMUSQO";
    var randRotorA = "ZGFHJLCPRXTVDNYEIWBAMUKOQS";
    var randRotorB = "VZBRGITYUPSDNHLXAWMJQOFECK";
    var randRotorC = "NYEIWGAKMUSQOBDFHJLCPRTXVZ";

    Console.WriteLine("Method 1: Rotor III -> Random Rotor A: {0}", 
        GetSimilarity1(rotorIII, randRotorA));
    Console.WriteLine("Method 1: Rotor III -> Random Rotor B: {0}", 
        GetSimilarity1(rotorIII, randRotorB));
    Console.WriteLine("Method 1: Rotor III -> Random Rotor C: {0}", 
        GetSimilarity1(rotorIII, randRotorC));

    Console.WriteLine("-----------------------------------------");

    Console.WriteLine("Method 2: Rotor III -> Random Rotor A: {0}", 
        GetSimilarity2(rotorIII, randRotorA));
    Console.WriteLine("Method 2: Rotor III -> Random Rotor B: {0}", 
        GetSimilarity2(rotorIII, randRotorB));
    Console.WriteLine("Method 2: Rotor III -> Random Rotor C: {0}", 
        GetSimilarity2(rotorIII, randRotorC));

    // Wait for input before closing
    Console.WriteLine("\nDone!\nPress any key to exit...");
    Console.ReadKey();
}

输出

NetMage 7 年前

https://www.dotnetperls.com/levenshtein