Случайное столкновение строк после использования алгоритма Фишера-Йейтса (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));
    }
}

После некоторого поиска, я наткнулся на пару решений и узнал об алгоритме Фишера-Йейтса. Я пытался внедрить его в свое собственное решение, но, к сожалению, я не смог пройти финальный тест, и я в замешательстве. Если бы кто-то мог указать мне правильное направление с этим, я был бы очень признателен. Мой код ниже:

РЕДАКТИРОВАТЬ: я забыл упомянуть, что формат строки должен следовать за этим: @ "^ [AZ] {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

Самым простым решением для уникальных имен является использование 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: Попробовал приведенный выше код и сгенерировал 10000 имен, используя случайные числа, полученные между 9915 и 9950 уникальными именами. Это не хорошо. Я бы использовал простой элемент c в классе как счетчик вместо генератора случайных чисел.

Answer 2

Первое правило любого идентификатора:

Не имеет значения, насколько оно велико, сколько оно может стоить - если вы просто создадите их достаточно, вы в конечном итоге получите коллизию. .

Цитировать Триллиана из Руководства Hithchikers: «[Разговор] не невозможен. Просто очень, очень маловероятно».

Однако в этом случае я думаю, что это вы создание случайных экземпляров в L oop. Это классическая ошибка начинающих при работе с Random . Вы не должны создавать новый случайный момент для каждого экземпляра робота, у вас должен быть один для приложения, которое вы используете повторно. Как и все генераторы псевдослучайных чисел, случайным является определение c. Те же входы - те же выходы.

Поскольку вы не указали начальное значение, оно будет использовать время в миллисекундах. Который идет к тому же между первыми 20+ l oop итерациями наконец. Так что он будет иметь одинаковое начальное число и одинаковые входы, поэтому одинаковые выходы.

Answer 3

Сначала давайте рассмотрим тест, в котором вы провалили код:

• 10.000 созданных экземпляров
• Все они должны иметь разные имена

Итак каким-то образом при создании 10000 «случайных» имен ваш код создает как минимум двух одинаковых имен.

Теперь давайте посмотрим на схему именования, которую вы используете:

AB123

Максимальное количество уникальных имен, которые мы могли бы создать, составляет 468000 (26 * 25 * 10 * 9 * 8).

Кажется, что это не должно быть проблемой, потому что 10000 < 468000 - но тут-то и начинается парадокс дня рождения !

Из википедии:

В теории вероятностей проблема дня рождения или парадокс дня рождения касается вероятности того, что в наборе из n случайно выбранных людей у ​​некоторой пары будет один и тот же день рождения.

Переписано для целей вашего проблема, в итоге мы спрашиваем:

Какова вероятность того, что в наборе O f 10000 случайно выбранных людей , некоторые пары из них будут иметь одно и то же имя .

В статье в Википедии также приведена функция для приблизительного определения количества людей Требуется для достижения вероятности 50%, что два человека будут иметь одно и то же имя:

, где m - общее количество возможных различных значений. Применение этого с m=468000 дает нам ~ 806 - это означает, что после создания только 806 случайно названных Robot с, уже есть 50% -ная вероятность того, что два из них будут иметь одно и то же имя. Робот # 10000, вероятность того, что не сгенерирует два одинаковых имени, в основном равна 0.

Как уже отмечали другие, вы можете решить эту проблему, используя Guid в качестве робота имя вместо

Если вы хотите сохранить соглашение об именах, вы также можете обойти это, внедрив LCG с соответствующим периодом и использовать его как менее подверженный столкновениям «генератор имен».

Answer 4

Вот один из способов сделать это:

1. Создать список всех возможных имен
2. Для каждого робота случайным образом выбрать имя из списка
3. Удалите выбранное имя из списка, чтобы оно не могло быть выбрано снова

При этом вам даже не нужно перемешивать. Примерно так (заметьте, я украл метод генерирования имен в 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);
    }
}

Вот скрипка , которая генерирует 20 случайных имен. Они могут быть уникальными только потому, что их удаляют после использования.

Однако вопрос о многоголовке очень важен . Если вам нужно было иметь возможность генерировать роботов параллельно, вам нужно добавить некоторый код (например, заблокировать критическую часть кода), чтобы гарантировать, что только одно имя выбрано и удалено из списка кандидатов в то или иное время будет очень плохо, очень быстро. Вот почему, когда людям нужен случайный идентификатор с разумным ожиданием того, что он будет уникальным, не беспокоясь о том, что некоторые другие потоки пробуют то же самое одновременно, они используют GUID. Огромное количество возможных GUID делает коллизии очень маловероятными. Но у вас нет такой роскоши с 676 000 возможных значений