随机放置非重叠区间

Question

我有一个区间G，和一组不同长度的非重叠子区间s₁, s₂, ..., s_n.

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

我正在寻找一种算法来获取所有这些子间隔，然后将它们再次随机放置在 G 上，这样它们就不会重叠。执行此操作的最佳方法是什么？

最简单、最幼稚的方法就是简单地随机 select 每个子区间的起始位置，在所有区间放置后检查重叠，如果有重叠则重新开始。如果子区间提供 G 的稀疏覆盖，这可能会非常快，但随着密度的增加，效率会越来越低。

类似的想法是在放置每个子间隔时检查重叠。不过，对效率也有类似的担忧。

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

更新

澄清几点：

就是我要随机分布的子区间间距
在这种情况下，均匀分布可能是最合适的随机性概念。
这些是离散（整数）闭区间，不是连续的。

Answer 1

是这样的吗？

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)

Answer 2

我认为 okio 的回答会给出有偏差的间隙分布（即第一个间隙往往比后面的间隙更大。

不过，我认为非常相似的方法应该效果更好：

将所有 sn 收缩为零长度
为 lenG-lenS 中的每个 sn 选择随机位置
将 sn 扩展回原来的长度

随机放置非重叠区间

Random placement of non-overlapping intervals

algorithm

random

intervals