我希望這是解決此類一般問題的正確論壇，請告訴我是否應該將其解決到其他地方。
我有一個 NxN 網格，我想在其中“隨機”放置 M 個專案，這些專案中的每一個都有一個唯一的 Id（整數）。每當我使用相同的一組專案（相同的 ID）進行此展示時，我都希望每個專案具有相同的分布。
基本上我需要構建一個放置函式，它將 Id 陣列作為輸入，并給出一個坐標陣列作為輸出，但我不知道如何開始。有什么建議？
uj5u.com熱心網友回復：
如果您嘗試根據各個 ID 值生成各個位置，您很可能會因生日問題而遇到沖突。您可以使用為哈希表開發的技術來解決這個問題，但是當 M 接近 N*N 時，這些技術會變得笨拙且可能很昂貴，因此我將您的問題解釋為同一組 ID 將生成相同的一組網格位置。
下面介紹的解決方案假設您可以訪問 PRNG，當給定相同的種子值時，它會產生相同的值流。ID 值（或它們的散列，如果它們是非數字的）以可重復的方式匯集以生成種子。我使用了 XORing，它避免了可能的溢位問題，但您可以將自己喜歡的映射從 ID 集替換為種子值。然后使用 PRNG 對從 0 到 (N*N)-1 的整數串列進行打亂，并選取前 M 個值。使用涉及除法的舊技巧將這些映射到二維坐標中以獲取行索引和模數以獲取列索引。由于保證 M 值是唯一的，因此相應的網格索引也是如此。這假設陣列索引是從零開始的，對于基于 1 的語言，通過添加 1 進行移位。它還假設您可以訪問 shuffle 方法。如果沒有，很容易實作一個費雪-耶茨洗牌。
不用多說，這里有一個 Ruby 中的大量注釋實作：
def grid_locs(ids, n )
# Generate a seed by XORing all of the ids with 0xFFFFFFFF
id_based_seed = ids.inject(0xFFFFFFFF) { |memo, x| memo ^ x }
# Use this to seed the built-in PRNG
srand(id_based_seed)
# Create an array containing the numbers 0 up to N*N - 1
unique_values = Array.new(n*n) { |i| i }
# Shuffle the array, pick off the first M values, convert them
# to 2-d indices using the ancient division & modulo trick, and
# return the results as a set of M unique grid locations
return unique_values.shuffle[0...ids.size].map do |index|
[index / n, index % n]
end
end
# Helper to print the 2-d grid
def print_2d(ary)
ary.each { |row| p row }
puts
end
# # I initially generated random IDs, but then stored them for reproducibility
# id = Array.new(5) { rand(1..0xFFFFFFFF) }
ids = [4146364446, 2782840243, 4137630311, 3993445117, 3133691672]
# Generate and print a grid of asterisks
two_d_table = Array.new(4) { |i| Array.new(4) { '*' } }
puts "Before:"
print_2d two_d_table
# Generate and print grid locations using the method above
locations = grid_locs(ids, two_d_table.size)
puts "Locations: #{locations.inspect}"
puts
# Place ID index at each of the generated locations and print the results
locations.each.with_index { |loc, i| two_d_table[loc[0]][loc[1]] = i }
puts "After:"
print_2d two_d_table
它產生：
Before:
["*", "*", "*", "*"]
["*", "*", "*", "*"]
["*", "*", "*", "*"]
["*", "*", "*", "*"]
Locations: [[0, 2], [3, 2], [3, 1], [1, 2], [2, 1]]
After:
["*", "*", 0, "*"]
["*", "*", 3, "*"]
["*", 4, "*", "*"]
["*", 2, 1, "*"]
給定相同的一組索引，位置是相同的，但會根據不同的索引數量或不同的索引值而改變。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/347691.html
標籤：算法
上一篇：理解像素在螢屏上的顯示