如何比较排列

Question

上下文

我正在构建一个基于 Enigma 的加密应用程序（为了好玩）。

（我把这个问题放在了 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 明显更加多样化。 Rotor C 看起来与 Rotor III 有很大不同 - 但实际上并不是，它只是 Rotor III 被切成两半，第二部分放在第一部分前面。

如何比较这种性质的字符串（或字符数组）？

仅供参考，我会使用 C# 来构建它，但很高兴接受我可以实现的任何合适的逻辑。

更新

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

Answer 1

我建议您看看使用 Levenshtein 距离。我认为你错了，根据使用它映射可见字母的结果，转子 C 与转子 B 一样不同。 similarity/difference 中重要的是对最终输出的影响。

https://www.dotnetperls.com/levenshtein

Answer 2

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

假设字符串的长度始终相同并且包含相同的字符，您可以通过以下几种方式来考虑相似性。一个是位于相同位置的字符的百分比，另一个是第二个字符串中所有字符与第一个字符串中的位置的距离的总百分比。

第一个很简单：

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 中减去该数字（从 "bad" 百分比（完全匹配为 0）转换为 "good" 百分比（完全匹配为 1））并乘以 100，将该数字转换为百分比。然后将此数字添加到运行总数中。

最后，将总数除以字符数得到最终的 "similarity" 百分比。

为了计算一个值可能与实际位置的最大距离，我将它在第一个数组中的索引值与 (length - index - 1) 的值进行比较，以较大者为准。索引字符可以是：

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();
}

输出

如何比较排列

How to compare permutations

c#

permutation

string-comparison