如何创建包含数字和字母的唯一字符串，而不会在使用后重复名称

Question

我正在尝试使用 C# 进行以下编码挑战：

Manage robot factory settings.

When a robot comes off the factory floor, it has no name.

The first time you turn on a robot, a random name is generated in the format of two uppercase letters followed by three digits, such as RX837 or BC811.

Every once in a while we need to reset a robot to its factory settings, which means that its name gets wiped. The next time you ask, that robot will respond with a new random name.

The names must be random: they should not follow a predictable sequence. Using random names means a risk of collisions. Your solution must ensure that every existing robot has a unique name.

我创建了一个机器人 class，它通过了我的 8 个单元测试中的 7 个。失败的是：

[Fact]
public void Robot_names_are_unique()
{
    const int robotsCount = 10_000;
    var robots = new List<Robot>(robotsCount); // Needed to keep a reference to the robots as IDs of recycled robots may be re-issued
    var names = new HashSet<string>(robotsCount);
    for (int i = 0; i < robotsCount; i++) {
        var robot = new Robot();
        robots.Add(robot);
        Assert.True(names.Add(robot.Name));
        Assert.Matches(@"^[A-Z]{2}\d{3}$", robot.Name);
    }
}

我检查了我的代码，我认为问题是因为我正在生成随机值，但在创建多个名称时我无法确保这些值是唯一的。这是我的 class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Robot
{
    Random random = new Random();
    Dictionary<string, bool> usedNames = new Dictionary<string, bool>();
    public Robot()
    {
        Name = RandomName();
    }

    private string _name;

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }


    public void Reset()
    {
        Name = RandomName();
    }

    private string RandomName()
    {
        Random rand = new Random();
        int nums = random.Next(000, 1000);
        var val = nums.ToString("000");
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string letters = new string(Enumerable.Repeat(chars, 2)
            .Select(s => s[random.Next(s.Length)]).ToArray());
        string name = $"{letters}{val}";
        if (usedNames.ContainsKey(name))
        {
// Implement here or refactor with loop?
        }
        return name;
    }
}

但是，在查看我的代码之后，我觉得有更好的方法。我当时认为该方法将涉及从头到尾依次遍历名称中可能的数字和字母，以确保每个名称都是唯一的。我在正确的轨道上吗？我可以做些什么更好？

Answer 1

使用random.choice到select2个随机字符和3个随机数

import random

def generate_license():
    letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    numbers = "0123456789"
    license = ""
    for i in range(2):
        license += random.choice(letters)
    for i in range(3):
        license += random.choice(numbers)
    return license

for i in range(30):
    print(generate_license())

输出：

FD508 FI820 TY975 NR415 GD041 IK313 GR103 WR994 PL631 WT808 紫外线119 KO727 LK584 GM629 BM545 VX728 UN773 AM000 UW267 KE949 KW182 TL030 YW536 AF038 PQ493 TT153 NP626 JK151 WA536 OU825

Answer 2

我们只有

26 * 26 * 1000 == 676000

可能的名字。让我们生成它们 all 和 shuffle。然后我们可以从names中一个接一个地取下一个机器人名字：

// Yates algorithm will be faster then ordering by random (here I've used Guid)
static string[] Names = Enumerable
  .Range(0, 26 * 26)
  .SelectMany(letters => Enumerable
     .Range(0, 1000)
     .Select(i => $"{(char)('A' + letters / 26)}{(char)('A' + letters % 26)}{i:000}"))
  .OrderBy(item => Guid.NewGuid())
  .ToArray();

static int currentIndex = -1;

// Interlocked: let's implement thread safe method 
static string NextName() => 
  Names[Interlocked.Increment(ref currentIndex) % Names.Length];

演示：

for (int i = 0; i < 10; ++i)
  Console.WriteLine(NextName());

结果：（可能因工作站而异）

JQ393
GQ249
JZ370
OC621
GD309
CP822
DK698
AD610
XY300
WV698

编辑： 如果我们想重用名称（当机器人设置为出厂默认设置时会被删除）我们可以使用Queue 而不是数组：

static ConcurrentQueue<string> Names = new ConcurrentQueue<string>(Enumerable
  .Range(0, 26 * 26)
  .SelectMany(letters => Enumerable
     .Range(0, 1000)
     .Select(i => $"{(char)('A' + letters / 26)}{(char)('A' + letters % 26)}{i:000}"))
  .OrderBy(item => Guid.NewGuid()));
  
static string NextName() => Names.TryDequeue(out string result) ? result : "???";

static string ScrapName(string name) => Names.Enqueue(name);

static string ResetName(string oldName) {
  string newName = Names.TryDequeue(out string result) 
    ? result 
    : "???";

  if (!string.IsNullOrEmpty(oldName))
    Names.Enqueue(oldName);

  return newName; 
}

Answer 3

一个选项是创建一个 class 来生成名称。 class 应该跟踪已经创建的名称。如果机器人数量不多，这种方法效果更好。

public class NameGenerator
{
    static HashSet<string> created = new HashSet<string>();
    static Random rand = new Random();
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    public static string GetName()
    {
        if (created.Count == 676000) {
            // Throw an exception?
        }

        string name;
        do {
            name = $"{chars[rand.Next(chars.Length)]}{chars[rand.Next(chars.Length)]}{rand.Next(0, 1000):D3}";
        } while (!created.Add(name));
        return name;
    }

    public static void Reset() {
        created = new HashSet<string>();
    }
}

一些快速分析：

Number of IDs generated	Time (s)	Time (ms) to create last	Approx. mem used (MB) }
1,000	~0	<1	0.05
10,000	0.005	<1	0.52
50,000	0.032	<1	2.4
100,000	0.078	<1	4.9
250,000	0.229	<1	11.1
500,000	0.626	<1	22.8
600,000	0.961	<1	25.1
625,000	1.143	<1	25.8
650,000	1.390	<1	26.3
676,000	5.386	293	38.5

显然，一旦接近 676,000 限制，就会有很大的增加。

Answer 4

有很多可能的名字。除非您计划拥有近 50 万个机器人，否则一个好的解决方案是创建一个自定义的、可重复使用的生成器来跟踪所有生成的名称。

public class UniqueNameGenerator
{
   private readonly HashSet<string> generatedNames;
   private readonly Random generator;

   public UniqueNameGenerator(Random random = null)
   {
      this.generatedNames = new HashSet<string>();
      this.generator = random ?? new Random();
   }

   public string GenerateName()
   {
      string name;

      do
      {
          name = this.TryGenerateName();
      }
      while(this.generatedNames.Contains(name));

      this.generatedNames.Add(name);
      return name;
   }

   private string TryGenerateName()
   {
      var nameBuilder = new StringBuilder();

      nameBuilder.Append(this.PickRandomLetter('A', 'Z'));
      nameBuilder.Append(this.PickRandomLetter('A', 'Z'));
      nameBuilder.Append(this.PickRandomNumber(0, 1000));

      return nameBuilder.ToString();
   }

   private int PickRandomNumber(int min, int max)
   {
      return this.generator.Next(min, max + 1);
   }

   private char PickRandomLetter(char from, char to)
   {
      var letterIndex = this.generator.Next((int)from, (int)to);
      return (char)letterIndex;
   }
}

在机器人 class 中保留一个静态实例，或者更好的是，创建一个 RobotFactory 来创建具有 UniqueNameGenerator 单个实例的机器人。

如何创建包含数字和字母的唯一字符串，而不会在使用后重复名称

How to create unique string containing numbers and letters without repeating name once used

c#

random