sql - 查找数据集的最少邮政编码算法

Question

我翻阅了所有美国邮政编码，搜索结果包括每次搜索的多个位置。我现在想弄清楚我需要搜索的最小邮政编码数量，以返回相同的唯一位置结果。例如，邮政编码 12345 返回商店 A、B、C、D，邮政编码 12347 返回 A、B、C，邮政编码 12349 返回 B、C、D；我只想获得 12345，因为它获得了所有商店。

Answer 1

我假设您的数据包含两列，邮政编码和存储。任何给定的邮政编码和商店都可能在数据中出现多次。

从技术上讲，您要的是一个覆盖集。每个邮政编码“覆盖”一组商店。您正在寻找尺寸最小（邮政编码最少）的覆盖物套装。

很容易得到一个覆盖集。这是一个例子：

select distinct zipcode
from (select store, min(zipcode) as zipcode
      from t
      group by store
     ) t

对此的修改可能会让你接近你想要的。对于每个商店，如果您选择覆盖该邮政编码最多商店的邮政编码，您将有一个贪心算法来选择覆盖集。这是一种方法：

select distinct zipcode
from (select store, zipcode
      from (select store, zipcode, count(*) as numstores,
                   row_number() over (partition by store order by count(*) desc) as seqnum
            from t
            group by store, zipcode
           ) t
      where seqnum = 1
     ) t

但是，贪心算法不能保证产生最小数量的邮政编码。不幸的是，我认为您的问题的一般解决方案在 SQL 中是不可行的，因为您需要考虑邮政编码的所有组合。然后确定覆盖所有商店的最小的那个。但是，上面的查询可能足以满足您的目的。

Answer 2

Select zip_code,max(stores) from (Select     zip_code,count(1) stores from mytable
Group by zip_code)