如何在Ruby中生成n个唯一随机数的列表?

时间:2020-03-06 14:34:48  来源:igfitidea点击:

这是我到目前为止的内容:

myArray.map!{ rand(max) }

但是,显然,列表中的数字有时不是唯一的。如何确保我的列表仅包含唯一数字,而不必创建更大的列表,然后从中选择n个唯一数字?

编辑:
如果可能的话,我真的很想看看这个完成的w / o循环。

解决方案

我们可以使用哈希来跟踪到目前为止使用的随机数:

seen = {}
max = 100
(1..10).map { |n|
  x = rand(max)
  while (seen[x]) 
    x = rand(max)
  end
  x
}

与其将项目添加到列表/数组中,不如将它们添加到集合中。

这使用Set:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    loop do
        randoms << rand(max)
        return randoms.to_a if randoms.size >= n
    end
end

这是一种解决方案:

假设我们希望这些随机数介于r_min和r_max之间。对于列表中的每个元素,生成一个随机数r,然后使list [i] = list [i-1] + r。这将为我们提供单调增加的随机数,并保证唯一性,前提是

  • r + list [i-1]不会溢出
  • r> 0

对于第一个元素,我们将使用r_min而不是list [i-1]。完成后,我们可以对列表进行混洗,以使元素的排列顺序不会那么明显。

这种方法的唯一问题是当我们遍历r_max并且仍然有更多要生成的元素时。在这种情况下,我们可以将" r_min"和" r_max"重置为我们已经计算出的2个相邻元素,然后简单地重复该过程。这样可以在没有数字使用的时间间隔内有效地运行相同的算法。我们可以继续执行此操作,直到填充列表为止。

(0..50).to_a.sort{ rand() - 0.5 }[0..x]

((0..50).to_a`可以替换为任何数组。
0是"最小值",50是"最大值"
x是"我想要多少个值"

当然,不可能让x大于max-min :)

扩展其工作原理

(0..5).to_a  ==> [0,1,2,3,4,5]
[0,1,2,3,4,5].sort{ -1 }  ==>  [0, 1, 2, 4, 3, 5]  # constant
[0,1,2,3,4,5].sort{  1 }  ==>  [5, 3, 0, 4, 2, 1]  # constant
[0,1,2,3,4,5].sort{ rand() - 0.5 }   ==>  [1, 5, 0, 3, 4, 2 ]  # random
[1, 5, 0, 3, 4, 2 ][ 0..2 ]   ==>  [1, 5, 0 ]

脚注:

值得一提的是,在最初回答此问题的时间(2008年9月)中," Array#shuffle"不可用或者我不知道,因此在" Array#sort"中是近似值。

结果,有大量建议对此进行编辑。

所以:

.sort{ rand() - 0.5 }

在使用以下代码的现代红宝石实现中可以更好,更短地表达

.shuffle

此外,

[0..x]

显然可以用Array#take编写为:

.take(x)

因此,在现代红宝石上生成随机数序列的最简单方法是:

(0..50).to_a.shuffle.take(x)

如果我们有一个可能的随机数的有限列表(即1到100),那么Kent的解决方案是不错的。

否则,没有其他好的方法可以做到不循环。问题是,如果得到重复,则必须循环执行。我的解决方案应该是有效的,并且循环不应超过数组的大小(即,如果我们想要20个唯一的随机数,则平均可能需要进行25次迭代。)尽管迭代次数越多,我们得到的数目就越多需要和较小的最大值是。这是我上面的代码经过修改,以显示给定输入需要多少次迭代:

require 'set'

def rand_n(n, max)
    randoms = Set.new
    i = 0
    loop do
        randoms << rand(max)
        break if randoms.size > n
        i += 1
    end
    puts "Took #{i} iterations for #{n} random numbers to a max of #{max}"
    return randoms.to_a
end

如果需要的话,我可以将此代码编写为更像Array.map的LOOK :)

最好事先知道最大值,我们可以这样做:

class NoLoopRand
  def initialize(max)
    @deck = (0..max).to_a
  end

  def getrnd
    return @deck.delete_at(rand(@deck.length - 1))
  end
end

我们可以通过以下方式获取随机数据:

aRndNum = NoLoopRand.new(10)
puts aRndNum.getrnd

当所有值从卡座中提取出来时,我们将获得" nil"。

为了让我们对速度有所了解,我运行了四个版本:

  • 像Ryan的建议一样使用Sets。
  • 使用稍微大于必要大小的Array,然后执行uniq!在最后。
  • 像Kyle建议的那样使用哈希。
  • 创建所需大小的数组,然后像Kent的建议一样对它进行随机排序(但没有多余的"-0.5",它什么也不做)。

它们在小规模时都很快,所以我让它们每个都创建了一个1,000,000个数字的列表。以下是时间,以秒为单位:

  • 套装:628
  • 数组+ uniq:629
  • 哈希值:645
  • 固定数组+排序:8

不,最后一个不是错字。因此,如果我们关心速度,并且数字可以是从0到整数的整数就可以了,那么我的确切代码是:

a = (0...1000000).sort_by{rand}

怎么玩呢?唯一的随机数,无需使用Set或者Hash。

x = 0
(1..100).map{|iter| x += rand(100)}.shuffle

是的,这样做可以没有循环,也无需跟踪选择了哪些数字。它被称为线性反馈移位寄存器:创建无重复的随机数序列