时间戳

首页 > 解决方案 > 需要一种算法进行连续性检查：选择一个整数列表以获得最佳“覆盖率”

algorithm - 需要一种算法进行连续性检查：选择一个整数列表以获得最佳“覆盖率”

问题描述

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

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

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

满足一个条件：新列表L2需要有最好的“覆盖”；
“覆盖”意味着L2中的所有元素整数需要尽可能平均地分布在L1的范围[A，B]中。（又名无偏的子抽样方法）

任何帮助都深表感谢。

感谢大家的帮助和想法。我试图简化问题，以便每个人（没有背景知识都可以理解问题）。要定义覆盖范围的优劣规则：

最终目标是实现：

  1. 在列表 L2 中，对于任意两个相邻元素 J 和 K，有 | J - K | ，并且这个差值的总和需要最小化

  2. 将总长度为 Q ( Q < M ) 的给定窗口应用于列表 L2，并且窗口内的元素数量需要相等（理想情况）或几乎相等

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

谢谢

标签： algorithmmathstatisticslinear-algebra

解决方案

我的想法是利用桶大小为 (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

推荐阅读