string - 任何使用数字作为生成随机字符串的提要的算法？

Question

我想生成一个任意固定长度 (N) 的随机字符串。使用与此算法的提要相同的数字，它应该生成相同的字符串。对像 number+1 这样的数字做一些小改动，它应该会生成一个完全不同的字符串。 (很难与前一个种子联系起来)如果多个数字可能导致相同的字符串，那也没关系。有什么方法可以做到这一点？

顺便说一下，我有一组字符要出现在字符串中，例如 A-Z a-z 0-9。

例如

Algorithm(54893450,4,"ABCDEFG0") -> A0GF
Algorithm(54893451,4,"ABCDEFG0") -> BDCG

我可以将每个字符一个一个地随机化，但是每个字符需要 N 个不同的种子。如果我想这样做，问题可能会变成“如何从一个数字生成 N 数字”作为种子。

最终目标是我想将 GUID 转换为在打印媒体上更易读且更短的内容。我不关心冲突。 (如果确实发生了冲突，我仍然可以检查 GUID 以解决问题)

Answer 1

好的，感谢@Jim Mischel 的指导。我阅读了所有相关页面并对此有了更多了解。

http://blog.mischel.com/2017/05/30/how-not-to-generate-unique-codes/

http://blog.mischel.com/2017/06/02/a-broken-unique-key-generator/

http://blog.mischel.com/2017/06/10/how-did-this-happen/

http://blog.mischel.com/2017/06/20/how-to-generate-random-looking-keys/

https://ericlippert.com/2013/11/12/math-from-scratch-part-thirteen-multiplicative-inverses/

https://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

总之，首先我应该使用一个序号。即 1,2,3,4,... 非常可预测，但它可能会变成随机且难以猜测的东西。

(请注意，在我的情况下，这并非完全可行，因为每个用户都将在本地生成自己的 ID，因此我无法运行全局序列号，因此我使用 GUID。但我会制定自己的解决方法以适应 GUID这个解决方案，可能在 GUID 上有一个简单的模数以使其适合我想要的范围。)

使用顺序整数 n 我可以通过乘法然后取模得到另一个看似无关的整数。这可能看起来像 (n * x)% m 和我选择的 x 和 m。当然 m 必须大于我想要使用的最大数字，因为它在乘法时环绕模数。

这本身就是一个好的开始，因为接近的数字 n 不提供类似的输出。但我们不能这么确定。例如，如果我的 x 是 4 而 m 是 16 那么输入只能产生 0,4,8,12。为避免这种情况，我们选择互质的 x 和 m。 (具有 1 的最大公约数)有许多明显的候选者，例如 100000 作为 m(将我的输出限制定义为 99999)和 2429 作为 x。如果我们这样选择2个互质数，不仅结果冲突尽可能小，而且保证每个输入在该范围内产生唯一的输出。

我们可以从这个例子中学习:

(n * 5) % 16

由于 5 和 16 是互质数，我们可以在循环之前得到最大长度的唯一数字序列。 (length = 16) 如果我们从 0 到 16 按顺序输入数字:

Input : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
Output : 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11, 0

我们可以看到输出的序列不是那么可预测的，而且除了最后一个输出之外没有任何输出是相同的。它会前往所有可能的可用号码。

现在，我非常可预测的连续运行数字将产生足够不同的数字，并且只要它在 m 的范围内，也保证不会与任何其他输入冲突。剩下的就是通过基本转换将这个数字转换为我选择的字符串。如果我有 5 个字符“ABCDE”，那么我将使用 base-5。

仅此就足以满足我的用例。但是利用乘法逆的概念，我还可以找到一个整数 y，它可以将乘法模变换反转为原始数。目前我还没有完全理解那部分，但它使用扩展欧几里得算法来找到y。

由于我的应用程序不需要还原，所以我暂时不了解它也没关系。我一定会尝试理解那部分。