在Ruby中需要一个包含字母数字的唯一随机字符串

Question

在Ruby中需要一个包含字母数字的唯一随机字符串

3

我正在使用以下代码在Ruby中生成一个由[A-Z a-z 0-9]组成的唯一10位随机字符串：

random_code = [*('a'..'z'),*('0'..'9'),*('A'..'Z')].shuffle[0, 10].join

然而，有时候随机字符串中并不包含数字或大写字母。您能帮忙编写一个方法来生成一个独特的随机字符串，该字符串至少包含一个数字、一个大写字母和一个小写字母吗？

- Snow Fox

2

由于您希望结果是随机的，但仍需要满足特定条件，所以需要谨慎处理。我建议先随机选择一个小写字母、一个大写字母和一个数字，然后再随机选取七个字符并将其全部打乱。 - Cary Swoveland

2

选择答案并不急迫。至少给它几个小时的时间。你不想打消其他人的积极性，可能会有更好或者更有趣的答案，而且快速选择也不被那些还在准备答案的人所欣赏。你刚刚选择了我的答案。请考虑暂时取消勾选。 - Cary Swoveland

1

@NguyenTuan你的代码返回了10个独特的字符（即没有重复的），这是一个要求吗？ - Stefan

1

“Unique random string” 没有意义。你的意思是（回答 @Stefan 的问题）字符串中每个字符仅出现一次吗？ - Cary Swoveland

2

你的示例返回10个唯一的字符，即字符串中的字符不会重复出现。就像从一个包含所有62个项目（a-z，A-Z，0-9）的罐子中抽取10个物品，而不将它们放回罐子中。这可能是你真正想要的，也可能不是。但是，不能保证以后不会再次抽取相同的10个物品。只是这种情况不太可能发生。 - Stefan

显示剩余8条评论

3个回答

4

如果您只想生成少量令牌（如2、5、10、100、1000、10000等），则最好的方法是将已生成的令牌保留在内存中，并重试，直到生成新的令牌（从统计学角度来看，这不会花费太长时间）。如果不是这种情况，请继续阅读。

经过思考，这个问题实际上非常有趣。为了简洁起见，我不会提及至少需要一个数字、大写和小写字母的要求，但将包含在最终解决方案中。另外，让 all = [*'1'..'9'，*'a'..'z'，*'A'..'Z'] 。

总之，我们想用唯一性约束随机生成n个元素的k排列。k = 10，n = 61（all.size）

Ruby刚好有这样的方法，它是Array#repeated_permutation。所以一切都很好，我们可以使用：

all.repeated_permutation(10).to_a.map(&join).shuffle

你可能会想逐个弹出生成的字符串，对吗？错！问题在于可能性的数量是：

k^n = 10000000000000000000000000000000000000000000000000000000000000 (10**61)。

即使您拥有一个无限快的处理器，您仍然无法保存这么多数据量，无论是复杂对象的计数还是简单位。

相反的方法是生成随机排列，在集合中保留已生成的排列，并在返回下一个元素之前进行包含检查。这只是推迟了不可避免的 - 不仅您最终仍然必须保存相同数量的信息，而且随着生成的排列数量增加，生成新排列所需的尝试次数会趋近于无穷大。

正如您可能已经想到的那样，问题的根源在于随机性和独特性很难同时存在。

首先，我们需要定义什么是随机的。从数量的书呆子漫画和主题中可以判断出，这也不是非黑即白的。

对于随机程序的一个直观定义将是每次执行时不以相同的顺序生成标记。很好，现在我们只需要取前n个排列（其中n = rand(100)），将它们放在最后并按顺序枚举所有内容？您可以感到这会导致什么。为了使随机生成被认为是好的，连续运行的生成输出应该均匀分布。简单地说，获得任何可能的输出的概率应该等于1 / #__all_possible_outputs__。

现在让我们探索一下问题的边界：

没有重复的n个元素的k排列的可能数量是：

n!/(n-k)! = 327_234_915_316_108_800 ((61 - 10 + 1).upto(61).reduce(:*))

仍然无法达到。同样适用于

没有重复的n个元素的全排列的可能数量：

n! = 507_580_213_877_224_798_800_856_812_176_625_227_226_004_528_988_036_003_099_405_939_480_985_600_000_000_000_000 (1.upto(61).reduce(:*))

不重复情况下，n个元素的可能k组合数：

n!/k!(n-k)! = 90_177_170_226 ((61 - 10 + 1).upto(61).reduce(:*)/1.upto(10).reduce(:*))

最后，我们可能会在没有重复的情况下完全排列k个元素：

k! = 3_628_800 (1.upto(10).reduce(:*))

约为3.5m，虽然不算小，但至少是可以计算的。在我的个人笔记本上，k_permutations = 0.upto(9).to_a.permutation.to_a 平均需要 2.008337 秒。一般来说，这是很长的计算时间。但是，假设你将在实际服务器上运行一次应用程序启动，那么这就不算什么了。事实上，甚至可以创建一些种子。单个 k_permutations.shuffle 花费 0.154134 秒，因此在大约一分钟内，我们可以获得 61 个随机排列：k_seeds = 61.times.map { k_permutations.shuffle }.to_a。

现在让我们尝试将n个元素的k排列问题转化为多次解决没有重复的k个完全排列问题。

生成排列的一个很酷的技巧是使用数字和位图。想法是生成所有从 0 到 2^61 - 1 的数字并查看位。如果位于位置 i 上有一个 1，我们将使用 all[i] 元素，否则我们将跳过它。我们仍然没有摆脱问题，因为 2^61 = 2305843009213693952 (2**61)，我们无法将其保存在内存中。

幸运的是，另一个很酷的技巧来自数论。

任意m个连续数对一个质数求模的幂次方的结果会给出从0到m-1的数字。

换句话说：

5.upto(65).map { |number| number**17 % 61 }.sort # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
5.upto(65).map { |number| number**17 % 61 } # => [36, 31, 51, 28, 20, 59, 11, 22, 47, 48, 42, 12, 54, 26, 5, 34, 29, 57, 24, 53, 15, 55, 3, 38, 21, 18, 43, 40, 23, 58, 6, 46, 8, 37, 4, 32, 27, 56, 35, 7, 49, 19, 13, 14, 39, 50, 2, 41, 33, 10, 30, 25, 16, 9, 17, 60, 0, 1, 44, 52, 45]

实际上，这有多随机呢？事实证明，m和所选的m个数字共享的公因数越多，序列分布就越不均匀。但我们很幸运-61^2-1是一个质数（也称为梅森质数）。因此，它能够共享的唯一除数是1和61^2-1。这意味着无论我们选择什么幂，数字0和1的位置都将被固定。这不是完美的，但其他61^2-3个数字可以在任何位置找到。猜猜怎么着-我们不关心0和1，因为它们的二进制表示中没有101！

不幸的是，我们的随机性瓶颈是我们想要生成的更大的质数越难生成。这是我能想出的最好方法，用于以随机顺序生成范围内的所有数字，而不需要同时将它们保留在内存中。

所以，为了把一切都应用起来：

1. 我们生成10个元素的全排列种子。 2. 我们生成一个随机质数。 3. 我们随机选择是否要为序列中的下一个数字生成排列，还是已经开始的数字（最多有限数量的已开始数字）。 4. 我们使用生成的数字的位图来获取所述排列。

请注意，这只解决了n个元素的k排列问题，没有重复。我仍然没有想到添加重复的方法。

免责声明：以下代码不提供任何形式的明示或暗示担保。它的目的是进一步表达作者的思想，而不是成熟的生产解决方案。

require 'prime'

class TokenGenerator
  NUMBERS_UPPER_BOUND = 2**61 - 1
  HAS_NUMBER_MASK     = ('1' * 9 + '0' * (61 - 9)).reverse.to_i(2)
  HAS_LOWER_CASE_MASK = ('0' * 9 + '1' * 26 + '0' * 26).reverse.to_i(2)
  HAS_UPPER_CASE_MASK = ('0' * (9 + 26) + '1' * 26).reverse.to_i(2)
  ALL_CHARACTERS = [*'1'..'9', *'a'..'z', *'A'..'Z']
  K_PERMUTATIONS = 0.upto(9).to_a.permutation.to_a # give it a couple of seconds

  def initialize
    random_prime = Prime.take(10_000).drop(100).sample

    @all_numbers_generator = 1.upto(NUMBERS_UPPER_BOUND).lazy.map do |number|
      number**random_prime % NUMBERS_UPPER_BOUND
    end.select do |number|
      !(number & HAS_NUMBER_MASK).zero? and
      !(number & HAS_LOWER_CASE_MASK).zero? and
      !(number & HAS_UPPER_CASE_MASK).zero? and
      number.to_s(2).chars.count('1') == 10
    end

    @k_permutation_seeds  = 61.times.map { K_PERMUTATIONS.shuffle }.to_a # this will take a minute
    @numbers_in_iteration = {go_fish: nil}
  end

  def next
    raise StopIteration if @numbers_in_iteration.empty?
    number_generator = @numbers_in_iteration.keys.sample

    if number_generator == :go_fish
      add_next_number if @numbers_in_iteration.size < 1_000_000
      self.next
    else
      next_permutation(number_generator)
    end
  end

  private
  def add_next_number
    @numbers_in_iteration[@all_numbers_generator.next] = @k_permutation_seeds.sample.to_enum
  rescue StopIteration # lol, you actually managed to traverse all 2^61 numbers!
    @numbers_in_iteration.delete(:go_fish)
  end

  def next_permutation(number)
    fetch_permutation(number, @numbers_in_iteration[number].next)
  rescue StopIteration # all k permutations for this number were already generated
    @numbers_in_iteration.delete(number)
    self.next
  end

  def fetch_permutation(number_mask, k_permutation)
    k_from_n_indices = number_mask.to_s(2).chars.reverse.map.with_index { |bit, index| index if bit == '1' }.compact
    k_permutation.each_with_object([]) { |order_index, k_from_n_values| k_from_n_values << ALL_CHARACTERS[k_from_n_indices[order_index]] }
  end
end

编辑：事实证明我们的约束条件排除了太多可能性。这导致@all_numbers_generator花费太多时间来测试和跳过数字。我会尝试想出一个更好的生成器，但其他所有内容仍然有效。

旧版本是在包含字符上具有唯一性约束的令牌生成器：

numbers          = ('0'..'9').to_a
downcase_letters = ('a'..'z').to_a
upcase_letters   = downcase_letters.map(&:upcase)
all = [numbers, downcase_letters, upcase_letters]
one_of_each_set  = all.map(&:sample)
random_code = (one_of_each_set + (all.flatten - one_of_each_set).sample(7)).shuffle.join

- ndnenkov

1

请注意 sample(7) 是不重复抽样。例如 7.times.to_a.sample(7) #=> => [0, 1, 4, 6, 2, 5, 3]。 - Cary Swoveland

@CarySwoveland，我不完全理解您所说的“无重复抽样”。您是指重复吗？能否解释一下？ - ndnenkov

在统计学中，你可以进行“有放回”或“无放回”的抽样。假设你有一个装有编号为1到6的六个球的容器，并且你希望随机抽取3个球的样本。如果是无放回抽样，你只需随机抽出3个球即可。它们当然会有不同的编号。如果是有放回抽样，你先抽出第一个球，记录其编号并放回容器中。然后你再抽出另一个球，记录其编号，放回并再次抽取第三个球。在后一种情况下，你可能会重复抽到第4个球。顺便说一句，似乎这里需要进行无放回抽样。 - Cary Swoveland

我明白了。我不知道这在英语中被称为“有放回抽样”。 - ndnenkov

在最后一行，您应该重复使用one_of_each_set变量来代替all.map(&:sample)，否则您将无法从大列表中删除相同的项目，并可能出现重复。 - Neil Slater

2

使用'SafeRandom'宝石 Github链接

它将提供最简单的方法为Rails 2、Rails 3、Rails 4、Rails 5生成随机值。

在这里，您可以使用strong_string方法生成强字符串组合（即字母（大写、小写）、数字和符号的组合）

# => Strong string: Minumum number should be greater than 5 otherwise by default 8 character string.
require 'safe_random'
puts SafeRandom.strong_string                   # => 4skgSy93zaCUZZCoF9WiJF4z3IDCGk%Y
puts SafeRandom.strong_string(3)                # => P4eUbcK%
puts SafeRandom.strong_string(5)                # => 5$Rkdo

- Rubyist

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cary Swoveland · Accepted Answer

down   = ('a'..'z').to_a
up     = ('A'..'Z').to_a
digits = ('0'..'9').to_a
all    = down + up + digits
[down.sample, up.sample, digits.sample].
  concat(7.times.map { all.sample }).
  shuffle.
  join
  #=> "TioS8TYw0F"

[编辑： 上述内容存在误解，但我将保留它。要使每个字符仅出现一次：

def rnd_str
  down   = ('a'..'z').to_a
  up     = ('A'..'Z').to_a
  digits = ('0'..'9').to_a
  [extract1(down), extract1(up), extract1(digits)].
    concat(((down+up+digits).sample(7))).shuffle.join
end

def extract1(arr)
  i = arr.size.times.to_a.sample
  c = arr[i]
  arr.delete_at(i)
  c
end

rnd_str #=> "YTLe0WGoa1" 
rnd_str #=> "NrBmAnE9bT"

down.sample.shift（等等）比extract1更为简洁，但是效率问题难以承受。

如果您不想重复随机字符串，只需保留您生成的字符串列表。如果您生成的另一个字符串已在列表中，则将其删除并生成另一个字符串。然而，您需要额外生成字符串的可能性非常小。例如，如果您生成了100个随机字符串（满足至少具有一个小写字母、大写字母和数字的要求），那么其中出现一个或多个重复字符串的概率约为70万分之一。

t = 107_518_933_731
n = t+1
t = t.to_f
(1.0 - 100.times.reduce(1.0) { |prod,_| prod * (n -= 1)/t }).round(10)
  #=> 1.39e-07

其中t = C(62,10)，且C(62,10)定义如下。

另一种方法

有一种非常简单的方法可以实现这一点，并且效率相当高：只需进行不重复采样，直到找到一个满足至少一个小写字母、一个大写字母和一个数字的样本。我们可以按照以下方式进行：

DOWN   = ('a'..'z').to_a
UP     = ('A'..'Z').to_a
DIGITS = ('0'..'9').to_a
ALL    = DOWN + UP + DIGITS

def rnd_str
  loop do
    arr = ALL.sample(10)
    break arr.shuffle.join unless (DOWN&&arr).empty? || (UP&&arr).empty? || 
    (DIGITS&&arr).empty?
  end
end

rnd_str #=> "3jRkHcP7Ge" 
rnd_str #=> "B0s81x4Jto

平均需要拒绝多少个样本才能找到一个“好”的样本？事实证明（如果您真的非常感兴趣，请参见下文），从所有62个元素中随机选择10个字符（不重复），没有小写字母、大写字母或数字的“坏”字符串的概率仅约为0.15（15%）。这意味着85%的时间在找到好的样本之前不会拒绝任何坏的样本。

事实证明，在找到好的字符串之前，预期会采样多少个坏的字符串是：

0.15/0.85 =~ 0.17

以下是上述概率的推导过程，如有兴趣请查看。

令 n_down 表示从字母表中抽取 10 个字符，且这些字符中没有小写字母的抽样方案数：

n_down = C(36,10) = 36!/(10!*(36-10)!)

其中（二项式系数）C(36,10)表示从36个“物品”中选取10个的组合数，等于：

C(36,10) = 36!/(10!*(36-10)!) #=> 254_186_856

同样地，

n_up = n_down #=> 254_186_856

并且

n_digits = C(52,10) #=> 15_820_024_220

我们可以将这三个数相加以获得：

n_down + n_up + n_digits #=> 16_328_397_932

这几乎是从10个字符中无重复地进行选择，并且不包含小写字母字符，大写字母或数字的方法数。但是由于存在一些重复计数，所以“几乎”不是完全正确的。必要的调整如下：

n_down + n_up + n_digits - 2*C(26,10) - 3
  #=> 16_317_774_459

为了得出从一个有62个元素的总体中无放回地抽取10个样本，这些样本既没有小写字母、大写字母也没有数字的概率，我们将这个数除以从62个元素中无放回地抽取10个字符的总方式数：

(16_317_774_459.0/c(62,10)).round(2)
  #=> 0.15