algorithm - 向数组添加或减去随机数以使数字的差值不超过 8 的算法

Question

可以从以下一组数字 {-8,-4,0,4,8} 中随机添加一系列 16 个数字，但考虑到新生成的系列不应该有任何两个数字相差8以上。

我正在尝试一种有效的算法，它可以生成一组数字，应该在不违反约束的情况下添加这些数字。

标签： algorithmoptimizationmathematical-optimization

Answer 1

如果您可以使用连续范围，则问题会稍微容易一些。这是一个在 Ruby 中被大量评论的实现：

# Note that generating from the set {-8, -4, 0, 4, 8} is equivalent to
# generating integers in the range -2..2 and scaling by 4.  Working with
# contiguous ranges is easier, just upscale before using or printing.

MAX_DELTA = 8 / 4   # specified maximum difference between any pair of values in scaled range
N = 16              # number of values to generate

data = []   # start with an empty array
data << rand(-2..2)   # generate first (anchor) value in rescaled range
(N - 1).times do      # generate remaining N-1 values by... 
  range_min, range_max = data.minmax    # finding min & max of current set
  # determine new range based on the current range + absolute constraints
  new_range_min = [range_max - MAX_DELTA, -2].max
  new_range_max = [range_min + MAX_DELTA,  2].min
  # generate and store new value
  data << rand(new_range_min..new_range_max)
end

# remap results to actual desired range
data.map! { |i| 4 * i }
# print results separated by commas.
puts data.join(', ')

这会产生如下输出：

4, -4, -4, 4, -4, 4, 0, 0, -4, -4, -4, 0, 0, 4, 4, -4

或者

4, 8, 8, 8, 8, 4, 4, 4, 0, 4, 8, 0, 0, 0, 4, 0