需要一个连续性检查算法：select 一个整数列表，以达到最佳 "coverage"

Question

这是我现在面临的一个核心算法问题：

假设有一个排序的整数列表 L1:
1.已知列表的总长度为N（例如N可以是1e7）
2. 所有元素都在两个已知边界 A 和 B 之间，( A <<< B )
例如L1 = [ 2,5,10,15,18,19,21...]

现在，我需要 select 列表 L1 中元素的子集以形成总长度为 M (M < N)
的新列表 L2 （例如 M 可以等于 N /10 ）

满足一个条件：新列表L2需要有最好的"coverage";
"coverage"表示L2中的所有元素整数需要尽可能均匀地分布在L1的[A,B]范围内。（a.k.a 一种无偏二次抽样方法）

非常感谢任何帮助。

感谢大家的帮助和想法。我尽量简化问题，以便每个人（没有背景知识也能理解问题）。定义覆盖率的规则：

最终目标是要达到：

在列表L2中，对于任意两个相邻元素J和K，有| J-K | , 并且这个差的总和需要最小化
将给定的 window 与 Q ( Q < M ) 的总长度应用于列表 L2，并且 window 中的元素数量需要相等（理想情况）或几乎等于

*最后更新：经过一番研究，原来这是Ip编程的一个著名问题，70年代的人已经解决了。更多详情请阅读论文：* http://www.geog.ucsb.edu/~forest/G294download/MAX_COVER_RLC_CSR.pdf

谢谢

Answer 1

我的想法是利用桶大小为(A - B) / M的桶排序。将l1中的每个元素映射到其对应的桶后，从每个桶中随机选择元素到新列表中。如果新列表比 m 短，则重复该过程。以下是我在Python中的实现：

import bisect
import random
import collections

def form_new_list(l1, m, a, b, res):
    if m <= 0:
        return

    bucket_size = int((b - a) / m)
    bucket_list = collections.defaultdict(list)
    for i, num in enumerate(l1):
        bucket_num = int(num / bucket_size)
        bucket_list[bucket_num].append(num)

    for _, nums in bucket_list.items():
        selected = random.choice(nums)
        position = bisect.bisect(res, selected)
        bisect.insort(res, selected)
        l1.remove(selected)

    form_new_list(l1, m - len(res), a, b, res)

    return res

需要一个连续性检查算法：select 一个整数列表，以达到最佳 "coverage"

need an algorithm for continuity check: select a list of integer number to have best "coverage"

algorithm

math

statistics

linear-algebra