logo标签列表

非重叠区间的随机放置

algorithmrandomintervals
10

我有一个区间G，以及一组长度不同的非重叠子区间s1, s2, ..., sn。

G |--------------------------------------------------------------// //-----------|
        s1 [---]                       s3 [------------------]
                    s2 [------]                                         sn [--]

我正在寻找一种算法，将所有这些子区间取出并随机放置到G上，以使它们不重叠。如何最好地做到这一点？

最简单、最朴素的方法是为每个子区间随机选择起始位置，在放置所有区间后检查是否有重叠，并在有重叠时重新开始。如果子区间对G提供了稀疏覆盖，则可能会非常快，但随着密度的增加而变得越来越低效。

一个类似的想法是在放置每个子区间时检查是否有重叠。虽然效率方面也存在类似的问题。

有没有更聪明的方法来处理这个问题呢？

更新

澄清一些问题：

  • 我希望随机分布的是子区间的间距。
  • 均匀分布可能是这种情况下最合适的随机性概念。
  • 这些是离散（整数）闭区间，而不是连续区间。
1
我认为你需要明确(1)你想要什么分布，以及(2)你想要随机分布的具体内容。子间隔的左侧、右侧(从左侧测量)、它们之间的间隙？一旦你明确了它们，就可以正式测试它们。 - user1666959
很好的问题：我想要子间隔的间距（以及它们之间的间隙）是随机分布的（可能是均匀分布）。 - Daniel Standage
我还缺少什么：子间隔长度的总和是一个数字S。 G-S是所有空间的总和。因此，您想要从均匀分布中绘制N + 1个随机数字（N-1将分离N个间隔，并且您希望在每个端点上再添加一个） ，以便它们的总和为G-S。 对吧？好问题。您介意告诉我它出现在哪里吗？ - user1666959
2个回答
9
我认为okio的答案会导致空隙分布有偏差（即前面的空隙往往比后面的更大）。
然而，我认为一个非常相似的方法应该效果更好：
1. 将所有sn缩小至零长度。 2. 为每个sn在lenG-lenS中选择随机位置。 3. 将sn扩展回其原始长度。
1
使用这个路由，步骤1是不必要的，因为步骤3会随机它们。 - Mark Peters
1
非常好的简单解决方案，但我认为您仍然需要随机选择位置的顺序。想象一下当lenG=lenS时的边缘情况，每个人都将在位置0上。 - biziclop
除非s1需要在s2之前等等，否则不然。 - biziclop
我可能会随机排列它们，使它们之间的间距比区间长，然后减少空白间隔直到适合为止。加入一些巧妙的魔法，使最后一个区间不总是靠在主区间的末尾。 - S. Buda
你应该将区间缩小到大小为1，而不是0，然后在[0，lenG-lenS + n)中选择n个不同的起始位置。如果顺序需要随机化，那么在恢复长度之前进行随机洗牌。 - rici
4
像这样吗？
lenG = length(G)
lenS = length(s1) + length(s2) + length(s3) + length(sn)

empty_place_available = lenG - lenS
current_position = 0;

sort sn randomly

loop for each sn
    rand = rand(0, empty_place_available)
    position[sn] = current_position + rand
    empty_place_available = empty_place_available - rand
    current_position = current_position + rand + length(sn)
3
首个间隔不会趋向于比后续的间隔更长吗？ - Peter de Rivaz
@PeterdeRivaz 没错，你是对的（花了我一些时间才明白为什么，但我懂了:D） - ôkio
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接