sql - データセットを見つけるためのアルゴリズム最小郵便番号.

Question

米国の郵便番号をすべて調べてみたところ、検索結果には 1 回の検索で複数の場所が含まれていました。同じ一意の場所の結果を返すために検索する必要がある郵便番号の最小数を把握したいと思います。たとえば、郵便番号 12345 は店舗 A、B、C、D を返し、郵便番号 12347 は A、B、C を返し、郵便番号 12349 は B、C、D を返します。すべてのストアを取得するので、12345 を取得したいと思います。

Answer 1

zipcode と store の 2 つの列を持つデータがあるとします。特定の郵便番号と店舗は、データ内に複数回表示される場合があります。

技術的には、あなたが求めているのはカバー セットです。各郵便番号は、一連の店舗を「カバー」します。最小サイズ (郵便番号が最も少ない) のカバー セットを探しています。

カバーセットを手に入れるのは簡単です。次に例を示します。

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

これを変更すると、必要なものに近づく可能性があります。各店舗について、その郵便番号のほとんどの店舗をカバーする郵便番号を選択すると、カバー セットを選択するための貪欲なアルゴリズムが得られます。1 つの方法を次に示します。

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)