如何生成相邻数字在指定范围内的随机唯一数?

How do you generate random unique numbers in which adjacent numbers are within a specified range?

提问人:Jonathan 提问时间:10/15/2018 更新时间:8/15/2020 访问量:143

问:

因此,假设我想生成一个介于 和 (排除)之间的随机整数数组,这些数组不重复。但我也想确保.应允许环绕,以便a[]n0nabs(a[i]-a[i+1]) < maxRange

abs(a[i]-(a[i+1]+a.length)) < maxRange || abs((a[i]+a.length)-a[i+1]) || abs(a[i]-a[i+1]) < maxRange.

永远是真的。例如,如果 ,则数组有效,因为 。n=6maxRange =2a={1,3,2,4,0,5}3-1 = 2, 3-2 = 1, 4-2 = 2, (0+n)-4 = 2, and (0+n)-5 = 1

但无效,因为 .a={0,3,2,4,1,5}3-0=3 and 4-1=3

差异的分布应该是均匀的,并且在abs(a[i]-(a[i+1]+a.length))1maxRange

我觉得一定已经有一种算法可以做到这一点,但我似乎无法通过谷歌搜索找到它(也许我使用了不正确的术语)。我能想到的唯一实现方法是暴力搜索每个可能的排列,并检查是否满足条件以确定有效的排列,然后随机选择其中之一。但是,对于较长的数组,这可能会变得非常昂贵。也许最好将其视为非重复的随机游走或其他东西。但我不确定如何实现它。有什么想法吗?与语言无关的解决方案会很棒。

为了提供一些额外的信息,我想用它来在具有微不足道的地理或 demes 的遗传算法中执行锦标赛选择。例如,个人 a[0] 和 a[1] 将参加比赛(根据健康状况选择获胜者),而失败者将被交叉/替换。然后是 a[2] 和 a[3] 等。我想这样做的原因是,我可以一次性评估所有个体,然后一次性完成交叉阶段,然后重复这些阶段直到完成。我想这样做的原因是,我可以保证每个人在每一代人中都经过评估,这与典型的稳态遗传算法不同。

随机 不可知 独特的 遗传算法

评论

0赞 Philippe Olivier 10/15/2018
少于 ~20 行代码的简单约束编程模型可以通过随机变量/值选择启发式非常有效地解决这个问题。查看 Google OR-Tools

答: 暂无答案