使用 Fisher-Yates 算法后的随机字符串碰撞 (C#)

Question

我正在做 exercism.io 的练习，其中我必须为机器人生成随机名称。在我完成这个测试之前，我能够通过大部分测试：

[Fact]
public void Robot_names_are_unique()
{
    var names = new HashSet<string>();
    for (int i = 0; i < 10_000; i++) {
        var robot = new Robot();
        Assert.True(names.Add(robot.Name));
    }
}

经过一番谷歌搜索后，我偶然发现了几个解决方案并发现了 Fisher-Yates 算法。我试图将它实现到我自己的解决方案中，但不幸的是，我未能通过最终测试，我被难住了。如果有人能为此指出正确的方向，我将不胜感激。我的代码如下：

编辑：我忘了提到字符串的格式必须遵循：@"^[A-Z]{2}\d{3}$"

public class Robot
{
string _name;
Random r = new Random();
string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string nums = "0123456789";

public Robot()
{
    _name = letter() + num();
}

public string Name
{
    get { return _name; }
}

private string letter() => GetString(2 ,alpha.ToCharArray(), r);

private string num() => GetString(3, nums.ToCharArray(), r);

public void Reset() => _name = letter() + num();

public string GetString(int length,char[] chars, Random rnd)
{
    Shuffle(chars, rnd);
    return new string(chars, 0, length);
}

public void Shuffle(char[] _alpha, Random r)
{


    for(int i = _alpha.Length - 1; i > 1; i--)
    {
        int j = r.Next(i);
        char temp = _alpha[i];
        _alpha[i] = _alpha[j];
        _alpha[j] = temp;
    }

}

}

Answer 1

任何ID的第一条规则是：

It does not mater how big it is, how many possible value it has - if you just create enough of them, you will get a colission eventually.

引用 Hithchikers 指南中的 Trillian 的话：“[A colission] 并非不可能。只是真的，真的不太可能。”

但是在这种情况下，我认为是你在循环中创建随机实例。这是一个classical beginners mistake when workign with Random。您不应该为每个机器人实例创建一个新的随机实例，您应该为您重复使用的应用程序创建一个随机实例。与所有伪随机数生成器一样，Random 是确定性的。相同的输入 - 相同的输出。

由于您没有指定种子值，它将使用以毫秒为单位的时间。最后，前 20 多个循环迭代之间的结果是一样的。所以它将有相同的种子和相同的输入，所以相同的输出。

Answer 2

唯一名称的最简单解决方案是使用 GUID。理论上，可以生成非唯一的 GUID，但它非常接近于零。

示例代码如下：

var newUniqueName = Guid.NewGuid().ToString();

当然 GUID 看起来不漂亮，但它们确实易于使用。

编辑：由于我错过了格式的附加要求，我发现 GUID 格式是不可接受的。

这也是一个简单的方法。由于格式是两个字母（26^2 个可能值）和 3 个数字（10^3 个可能值），最终可能值的数量是 26^2 * 10^3 = 676 * 1000 = 676000。这个数字非常小，所以随机可用于生成 0-675999 范围内的随机整数，然后将该数字转换为名称。这是示例代码：

            var random = new System.Random();
            var value = random.Next(676000);
            var name = ((char)('A' + (value % 26))).ToString();
            value /= 26;
            name += (char)('A' + (value % 26));
            value /= 26;
            name += (char)('0' + (value % 10));
            value /= 10;
            name += (char)('0' + (value % 10));
            value /= 10;
            name += (char)('0' + (value % 10));

关于可能的相同名称的通常免责声明也适用于此，因为我们有 676000 个可能的变体和 10000 个必需的名称。

EDIT2：尝试了上面的代码并使用在 9915 到 9950 个唯一名称之间产生的随机数生成 10000 个名称。那可不行。我会在 class 成员中使用一个简单的 static 作为计数器而不是随机数生成器。

Answer 3

首先，让我们回顾一下您的代码未通过的测试：

创建了 10.000 个实例
必须全部具有不同的名称

所以不知何故，当创建 10000 个 "random" 名称时，您的代码会生成至少两个相同的名称。

现在，让我们看看您使用的命名方案：

AB123

我们可以创建的唯一名称的最大数量是 468000 (26 * 25 * 10 * 9 * 8)。

这似乎不成问题，因为 10000 < 468000 - 但这是 birthday paradox 的用武之地！

来自维基百科：

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday.

为了您的问题而重写，我们最终会问：

What's the probability that, in a set of 10000 randomly chosen people, some pair of them will have the same name.

维基百科文章还列出了一个函数，用于估算达到 50% 概率两个人同名所需的人数：

$BirthdayProblemApproxN$

其中 m 是可能的不同值的总数。将此与 m=468000 一起应用会得到 ~806 - 这意味着在仅创建 806 个随机命名的 Robot 之后，其中两个具有相同名称的可能性已经达到 50%。

当你到达 Robot #10000 时，not 生成两个相同名称的机会基本上为 0。

正如其他人所指出的，您可以通过使用 Guid 作为机器人名称来解决此问题。

如果您想保留命名约定，您也可以通过实施带有适当句点的 LCG 来解决这个问题，并将其用作不易发生冲突的 "naming generator".

Answer 4

这是您可以做到的一种方法：

生成所有可能名称的列表
对于每个机器人，select从列表中随机取一个名字
从列表中删除 selected 名称，这样它就不能再被 selected

有了这个，你甚至不需要洗牌。像这样（注意，我偷用了 Optional Option 的生成名称的方法，因为它很聪明，我懒得想自己的）：

public class Robot
{
    private static List<string> names;
    private static Random rnd = new Random();
    public string Name { get; private set; }

    static Robot()
    {
        Console.WriteLine("Initializing");
        // Generate possible candidates
        names = Enumerable.Range(0, 675999).Select(i => 
        {
            var sb = new StringBuilder(5);
            sb.Append((char)('A' + i % 26));
            i /= 26;
            sb.Append((char)('A' + i % 26));
            i /= 26;
            sb.Append(i % 10);
            i /= 10;
            sb.Append(i % 10);
            i /= 10;
            sb.Append(i % 10);
            return sb.ToString();
        }).ToList();
    }

    public Robot()
    {
        // Note: if this needs to be multithreaded, then you'd need to do some work here
        // to avoid two threads trying to take a name at the same time
        // Also note: you should probably check that names.Count > 0 
        // and throw an error if not
        var i = rnd.Next(0, names.Count - 1);
        Name = names[i];
        names.RemoveAt(i);
    }
}

这里有一个 fiddle 可以生成 20 个随机名称。它们只能是唯一的，因为它们一旦被使用就会被移除。

不过，关于多线程的要点非常重要。如果您需要能够并行生成机器人，那么您需要添加一些代码（例如锁定代码的关键部分）以确保 只有一个 名称被选中并且一次从候选人名单中删除，否则事情会很快变得非常糟糕。这就是为什么当人们需要一个随机 ID 并合理期望它是唯一的，而不用担心其他线程同时尝试相同的事情时，他们会使用 GUID。可能的 GUID 的绝对数量使得冲突的可能性很小。但是你没有那种只有 676,000 个可能值的奢侈

使用 Fisher-Yates 算法后的随机字符串碰撞 (C#)

Random string collision after using Fisher-Yates algorithm (C#)

c#

string

algorithm

name-collision