ruby - 在固定大小的数组上展开选择的算法

Question

这不是特定的 ruby​​ 问题:更多是关于算法的一般性问题。但是可能有一些特定于 ruby​​ 的数组方法很有用。

我有一个包含 30 个项目的数组。我要求 15 到 30 之间的一些项目，我想从整个数组中选择尽可能均匀分布的给定数量的项目。选择需要是非随机的，每次都返回相同的结果。

假设有人要 16 件商品。如果我返回前 16 个，那将是一个巨大的失败。相反，我可以返回所有奇数编号加上最后一个；如果我将数字 1 到 30 存储在数组中，我可以回馈

myArr.spread(16)
=> [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,30]

如果有人要求 20 件商品，这就有点棘手了:我无法立即想到一种好的编程方式来执行此操作。我觉得它一定已经被某人解决了。有什么建议么？

Answer 1

受 Alex D 的启发，我最终这样做了:我单步执行 n-1 次，然后始终将最后一个元素添加到末尾。

class Array
  def spread(n)
    step = self.length.to_f / (n -1) 
    (0..(n-2)).to_a.collect{|i| self[i * step]} + [self.last]
  end
end

 > (1..30).to_a.spread(3)
 => [1, 16, 30] 
 > (1..30).to_a.spread(4)
 => [1, 11, 21, 30] 
 > (1..30).to_a.spread(5)
 => [1, 8, 16, 23, 30] 
 > (1..30).to_a.spread(15)
 => [1, 3, 5, 7, 9, 11, 13, 16, 18, 20, 22, 24, 26, 28, 30]