在固定大小的数组上传播选择的算法

这不是一个特别的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个项目，它需要一点小技巧：我不能马上想到这样做的一个很好的编程方法。我觉得它一定已经被某人解决了。有什么建议么？

来源

2012-08-10 Max Williams

除以要选择（不要使用截断司）的项目数的数组的大小 - 这将是你的“步幅”为你走过阵列，选择项目。继续将“步幅”添加到运行总数，直到它等于或超过数组的大小。每次添加“步幅”时，取整数部分并将其用作数组中的索引以选择一个项目。

假设你有100个项目，你想选择30.然后你的“步幅”将是3.3333 ...所以你以3.3333的“运行总数”开始，然后选择项目3.然后6.66666 - 所以你选择项6.接下来是10.0 - 让您选择项目10等等......

测试，以确保你没有“的一休”的错误得到，也不要被划分如果要选择的数组大小或项数为零，则为零。还要使用guard子句来确保要选择的项数不大于数组中的数字。

来源

2012-08-10 15:08:34

这听起来像贾斯汀高的答案，确实有点下滑（见评论）。 – 2012-08-13 12:27:40

@MaxWilliams，为了达到你想要的效果，你只需要调整一下使用的数字：而不是'array_size/number_to_select'，你可以使用'（array_size-1）/（number_to_select-1）'作为“stride ”。计数从0到'number_to_select-1'，并在每一步乘以“步幅”。 – 2012-08-13 12:47:47

-1

你可以尝试使用Random(doc)有固定的种子：

与Random对象，你可以挑选数组的元素随机
固定种子确保每次调用函数将生成随机数列表。

例如与Array#sample

def spread(arr, count) do 
    arr.sample(count, Random.new(0)) 
end

来源

2012-08-10 14:52:11 Baldrick

感谢Baldrick但就像我在这个问题上很多其他的答案说，我不是找一个随机抽样，我正在寻找一个均匀分布的样本。 – 2012-08-13 12:32:36

有此here过类似的问题，但解决方案是蟒蛇。

在Ruby中，这将是：

class Array 
    def spread(count) 
     length = self.length 
     result = Array.new 
     0.upto(count-1) do |i| 
      result << self[(i * length.to_f/count).ceil] 
     end 
     return result 
    end 
end 

arr = Array(1..30) 
puts arr.spread(20) 
#=> [1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 30]

来源

2012-08-10 15:23:37

谢谢贾斯汀 - 这很好，但往往不会返回“count”小值的最后一个元素。例如，如果我做了'（1..30）.to_a.spread（3）'我期望'[1,15,30]'或'[1,16,30]'，但是我得到了'[1,11 ，21]'。这是因为你要循环计数-1。 – 2012-08-13 12:26:35

我落得这样做，由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]

来源

2012-08-13 13:02:16

最近刚刚实现了这个方法，但我把它叫做一个备份保留应用keep - 用于使用，我想我会分享我的解决方案。它类似于亚历克斯·D的答案与算法两个主要区别：

“跨越”是使用(length + (length/n) - 1).to_f/n其中n是所需物品的数量来计算。根据n进入length的次数计算偏移确保始终包含最后一个项目。
它使用模运算而不是递增：如果元素的索引除以“stride”的余数在0和1之间（包括0，不包括1），则元素将包含在结果中。 0 % x始终为0的事实确保始终返回第一个元素。
边缘情况下，例如当元素数量少于所需数量时，将被考虑。

class Array 
    def keep(n) 
    if n < 1 
     [] 
    elsif length <= n 
     self.clone 
    else 
     stride = (length + (length/n) - 1).to_f/n 
     select.with_index do |_, i| 
     remainder = i % stride 
     (0 <= remainder && remainder < 1) 
     end 
    end 
    end 
end

来源

2013-10-22 22:40:10 marxarelli

在固定大小的数组上传播选择的算法

回答

相关问题