洗牌和切片 Ruby 数组时防止相同对

Question

我想在 Ruby 数组中生成一组随机对时避免生成具有相同项目的对。

例如：

[1,1,2,2,3,4].shuffle.each_slice(2).to_a

可能产生：

[[1, 1], [3, 4], [2, 2]]

我希望能够确保它产生如下结果：

[[4, 1], [1, 2], [3, 2]]

在此先感谢您的帮助！

Answer 1

你可以看看有没有数学再洗牌:

a = [1,1,2,2,3,4]
# first time shuffle
sliced = a.shuffle.each_slice(2).to_a
# checking if there are matches and shuffle if there are
while sliced.combination(2).any? { |a, b| a.sort == b.sort } do
    sliced = a.shuffle.each_slice(2).to_a
end

不太可能，注意无限循环的可能性

Answer 2

arr = [1,1,2,2,3,4]
loop do
  sliced = arr.shuffle.each_slice(2).to_a
  break sliced if sliced.none? { |a| a.reduce(:==) }
end

Answer 3

这里有三种方法可以产生所需的结果（不包括重复采样直到找到有效样本的方法）。以下数组将用于说明。

arr = [1,4,1,2,3,2,1]

使用Array#combination and Array#sample

如果样本对允许两次具有相同的数字，样本 space 将是

arr.combination(2).to_a
  #=> [[1, 4], [1, 1], [1, 2], [1, 3], [1, 2], [1, 1], [4, 1], [4, 2],
  #    [4, 3], [4, 2], [4, 1], [1, 2], [1, 3], [1, 2], [1, 1], [2, 3],
  #    [2, 2], [2, 1], [3, 2], [3, 1], [2, 1]]

两次包含相同值的对——此处为 [1, 1] 和 [2, 2]——不需要，因此可以简单地将它们从上述数组中删除。

sample_space = arr.combination(2).reject { |x,y| x==y }
  #=> [[1, 4], [1, 2], [1, 3], [1, 2], [4, 1], [4, 2], [4, 3],
  #    [4, 2], [4, 1], [1, 2], [1, 3], [1, 2], [2, 3], [2, 1],
  #    [3, 2], [3, 1], [2, 1]]

我们显然要从 sample_space 中采样 arr.size/2 个元素。根据是否要完成 with or without replacement 我们会写

sample_space.sample(arr.size/2)
  #=> [[4, 3], [1, 2], [1, 3]]

用于无放回抽样和

Array.new(arr.size/2) { sample_space.sample }
  #=> [[1, 3], [4, 1], [2, 1]]

用于放回抽样。

按顺序对每对元素进行采样，方法 1

这个方法和下一个一样，只能用于有放回的采样。

让我们首先考虑对一对进行采样。我们可以通过从 arr 中随机选择该对的第一个元素，删除 arr 中该元素的所有实例，然后从 arr.[= 的剩余部分中采样第二个元素来做到这一点。 57=]

def sample_one_pair(arr)
  first = arr.sample
  [first, second = (arr-[first]).sample]
end

要抽取 arr.size/2 对样本，我们执行以下操作。

Array.new(arr.size/2) { sample_one_pair(arr) }
   #=> [[1, 2], [4, 3], [1, 2]]

按顺序对每对元素进行采样，方法 2

此方法是一种非常快速的方法，可以通过替换对大量对进行采样。和前面的方法一样，不放回就不能用来采样

首先，计算cdf（累积分布函数）随机绘制arr的一个元素。

counts = arr.group_by(&:itself).transform_values { |v| v.size }
  #=> {1=>3, 4=>1, 2=>2, 3=>1}

def cdf(sz, counts)
  frac = 1.0/sz
  counts.each_with_object([]) { |(k,v),a|
    a << [k, frac * v + (a.empty? ? 0 : a.last.last)] }
end

cdf_first = cdf(arr.size, counts)
  #=> [[1, 0.429], [4, 0.571], [2, 0.857], [3, 1.0]]

这意味着随机抽到一个1的概率为0.429（四舍五入），抽到一个1或一个4的概率为0.571，抽到一个[=的概率为0.857 31=、4 或 2 和 1.0 抽取四个数字之一。因此，我们可以通过获得零和一之间的（伪）随机数（p = rand）从arr中随机抽取一个数字，然后确定counts_cdf、[=40=的第一个元素] 其中 p <= q:

def draw_random(cdf)
  p = rand
  cdf.find { |n,q| p <= q }.first
end

draw_random(counts_cdf) #=> 1
draw_random(counts_cdf) #=> 4
draw_random(counts_cdf) #=> 1
draw_random(counts_cdf) #=> 1
draw_random(counts_cdf) #=> 2
draw_random(counts_cdf) #=> 3

顺便说一句，在仿真模型中，这是从离散概率分布生成伪随机变量的标准方法。

在绘制该对的第二个随机数之前，我们需要修改 cdf_first 以反映第一个数字无法再次绘制的事实。假设要随机生成许多对，最有效的方法是构造一个散列 cdf_second，其键是为该对随机抽取的第一个值，其值是相应的 cdf。

cdf_second = counts.keys.each_with_object({}) { |n, h|
  h[n] = cdf(arr.size - counts[n], counts.reject { |k,_| k==n }) }
  #=> {1=>[[4, 0.25], [2, 0.75], [3, 1.0]],
  #    4=>[[1, 0.5], [2, 0.833], [3, 1.0]],
  #    2=>[[1, 0.6], [4, 0.8], [3, 1.0]],
  #    3=>[[1, 0.5], [4, 0.667], [2, 1.0]]}

例如，如果为该对的第一个元素绘制 2，则为第二个元素绘制 1 的概率为 0.6，0.8 绘制 1 或 4 和 1.0 绘制 1、4 或 3.

然后我们可以按如下方式对一对进行采样。

def sample_one_pair(cdf_first, cdf_second)
  first = draw_random(cdf_first)
  [first, draw_random(cdf_second[first])]
end

和以前一样，要对 arr.size/2 个值进行替换采样，我们执行

Array.new(arr.size/2) { sample_one_pair }
  #=> [[2, 1], [3, 2], [1, 2]]

Answer 4

替换后，您可能会得到如下结果：

unique_pairs([1, 1, 2, 2, 3, 4]) # => [[4, 1], [1, 2], [1, 3]]

请注意 1 被选中了三次，即使它只在原始数组中被选中了两次。这是因为 1 每次被选中时都是 "replaced"。换句话说，它被放回 collection 中，有可能再次被选中。

这是 Cary 出色的 sample_one_pair 解决方案的一个版本没有替换：

def unique_pairs(arr)
  dup = arr.dup

  Array.new(dup.size / 2) do
    dup.shuffle!

    first = dup.pop
    second_index = dup.rindex { |e| e != first }
    raise StopIteration unless second_index
    second = dup.delete_at(second_index)

    [first, second]
  end
rescue StopIteration
  retry
end

unique_pairs([1, 1, 2, 2, 3, 4]) # => [[4, 3], [1, 2], [2, 1]]

这通过创建原始数组的副本并在选择元素时从中删除元素（因此不能再次选择它们）来实现。 rescue/retry 在那里，以防无法生成正确数量的对。例如，如果首先选择 [1, 3]，然后选择 [1, 4]，则不可能形成三个唯一的对，因为只剩下 [2, 2]；样本 space 已用完。

~~这应该比 Cary 的解决方案（有替换）慢，但（平均）比发布的需要循环和重试的解决方案（无替换）快。~~ 好吧，加油"always benchmark!" 的另一点我对 ~~all~~ 的大部分假设都是错误的。这是我的机器上的结果，包含 16 个数字 ([1, 1, 2, 2, 3, 4, 5, 5, 5, 6, 7, 7, 8, 9, 9, 10])：

cary_with_replacement
                         93.737k (± 2.9%) i/s -    470.690k in   5.025734s
mwp_without_replacement
                        187.739k (± 3.3%) i/s -    943.415k in   5.030774s
mudasobwa_without_replacement
                        129.490k (± 9.4%) i/s -    653.150k in   5.096761s

编辑：我更新了上述解决方案以解决 Stefan 的众多问题。事后看来，错误是显而易见的，令人尴尬！从好的方面来说，修改后的解决方案现在比 mudasobwa 的解决方案更快，而且我已经确认这两个解决方案具有相同的偏差。

洗牌和切片 Ruby 数组时防止相同对

Prevent identical pairs when shuffling and slicing Ruby array

ruby

arrays

shuffle