随机放置非重叠间隔

Question

我有一个区间G,以及一组不同长度的非重叠子区间s ₁,s ₂,...,s _n.

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

我正在寻找一种算法来获取所有这些子间隔,然后将它们再次放在G上,这样它们就不会重叠.做这个的最好方式是什么？

最简单,最天真的方法是简单地随机选择每个子区间的起始位置,一旦放置所有区间就检查重叠,然后如果存在重叠则重新开始.如果子间隔提供G的稀疏覆盖,但随着密度的增加,效率会越来越低,这可能会非常快.

类似的想法是在放置每个子间隔时检查重叠.然而,对效率的类似担忧.

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

UPDATE

澄清几点:

• 它是我想随机分布的子间隔的间距.
• 在这种情况下,均匀分布可能是最合适的随机概念.
• 这些是离散的(整数)闭合间隔,而不是连续的.

Answer 1

我认为okio的答案会给出差距的偏差分布(即第一个差距往往会比后来的差距更大.

但是,我认为一种非常类似的方法应该更好:

1. 将所有sn缩小到零长度
2. 为lenG-lenS中的每个sn选择随机位置
3. 将sn扩展回原始长度