在固定大小的數組上傳播選擇的算法

這不是一個特別的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

在固定大小的數組上傳播選擇的算法

回答

相關問題