ソートされたリストのソートされた合計を効率的に取得する

StackOverflow https://stackoverflow.com/questions/826

  •  08-06-2019
  •  | 
  •  

質問

数値の昇順リストがあります。そのリスト内の 2 つの数値ごとの合計の昇順リストを取得するために考えられる最も効率的なアルゴリズムは何ですか。結果のリスト内の重複は無関係なので、必要に応じて削除または回避できます。

はっきり言っておきますが、私はアルゴリズムに興味があります。好きな言語やパラダイムで自由にコードを投稿してください。

役に立ちましたか？

解決

2018年時点で編集：おそらくこれを読むのをやめたほうがいいでしょう。（ただし、承認されているため削除できません。）

合計を次のように書き出すと、

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

M[i,j] <= M[i,j+1] および M[i,j] <= M[i+1,j] であるため、左上のみを調べる必要があることがわかります。コーナー」を選択し、最も低いものを選択します。

例えば

  • 左上隅は 1 つだけ、2 つ選択
  • 1 つだけ、5 つ選んでください
  • 6 か 8、6 を選択してください
  • 7 か 8、7 を選択してください
  • 9 か 8、8 を選択してください
  • 9 か 9、両方選んでください:)
  • 10 または 10 または 10、すべて選択してください
  • 12 か 11、11 を選択してください
  • 12 または 12、両方を選択してください
  • 13 または 13、両方を選択してください
  • 14 または 14、両方を選択してください
  • 15 か 16、15 を選択してください
  • 1 つだけ、16 を選択
  • 1 つだけ、17 を選択
  • 1 つだけ、18 を選択

もちろん、持っているときは、 たくさん 左上隅の部分でこの解決策が展開されます。

この問題は Ω(n²) であると確信しています。なぜなら、誰かがより良い合計アルゴリズムを持っていない限り、各 M[i,j] の合計を計算する必要があるからです:)

他のヒント

これをコーディングするのではなく、段階的に疑似コーディングしてロジックを説明し、必要に応じてより優れたプログラマーが私のロジックに穴をあけられるようにしようと考えています。

最初のステップでは、長さ n の数値のリストから始めます。数値自体に数値を追加するわけではないので、数値ごとに長さ n-1 のリストを作成する必要があります。最終的には、O(n^2) 時間で生成された約 n 個のソートされたリストのリストが完成します。

step 1 (startinglist) 
for each number num1 in startinglist
   for each number num2 in startinglist
      add num1 plus num2 into templist
   add templist to sumlist
return sumlist

ステップ 2 では、リストが設計に従ってソートされているため (ソートされたリストの各要素に番号を追加すると、リストは引き続きソートされます)、ロット全体をマージソートするのではなく、各リストをマージするだけでマージソートを実行できます。最終的には O(n^2) 時間がかかるはずです。

step 2 (sumlist) 
create an empty list mergedlist
for each list templist in sumlist
   set mergelist equal to: merge(mergedlist,templist)
return mergedlist

マージ方法は、重複した合計がないことを確認するチェックを伴う通常のマージ ステップになります。マージソートについては誰でも調べることができるので、ここでは書きません。

そこで私の解決策があります。アルゴリズム全体には O(n^2) 時間がかかります。間違いや改善点があれば遠慮なくご指摘ください。

Python では次の 2 行でこれを行うことができます

allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)

このコストは、反復の場合は n^2 (セットの追加の対数係数でしょうか?)、ソートの場合は s * log(s) です。s はセットのサイズです。

たとえば、X = [1,2,4,...,2^n] の場合、セットのサイズは n*(n-1)/2 まで大きくなる可能性があります。したがって、このリストを生成したい場合、これが出力のサイズであるため、最悪の場合でも少なくとも n^2/2 かかります。

ただし、結果の最初の k 要素を選択したい場合は、Frederickson と Johnson による並べ替えられた X+Y 行列の選択アルゴリズムを使用して、O(kn) でこれを行うことができます (悲惨な詳細についてはここを参照してください）. 。ただし、計算を再利用してオンラインで生成し、このセット用の効率的なジェネレーターを取得するようにこれを変更することは可能です。

@deuseldorf、ピーター（n！）私は、deuseldorfが「n要因」を意味したが、単に「n、（非常に興奮している）を意味していることを真剣に疑います！​​」

私が思いつく最善の方法は、各ペアの合計の行列を生成し、行をマージしてマージ ソートすることです。はるかに効率的な解決策を明らかにするための簡単な洞察が欠けているように感じます。

Haskell での私のアルゴリズム:

matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]

sortedSums = foldl merge [] matrixOfSums

--A normal merge, save that we remove duplicates
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case compare x y of
    LT -> x:(merge xs (y:ys))
    EQ -> x:(merge xs (dropWhile (==x) ys))
    GT -> y:(merge (x:xs) ys)

私は、遅延ストリームベースのコーディングに適した小さな改善を見つけました。列をペアごとにマージするのではなく、すべてを一度にマージします。利点は、リストの要素の取得をすぐに開始できることです。

-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists
-- wideNubMerge does this while eliminating duplicates
wideNubMerge :: Ord a => [[a]] -> [a]
wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls
wideNubMerge1 [] = []
wideNubMerge1 ls = mini:(wideNubMerge rest)
    where mini = minimum $ map head ls
          rest = map (dropWhile (== mini)) ls

betterSortedSums = wideNubMerge matrixOfSums

ただし、すべての合計を使用することがわかっていて、一部を早く取得してもメリットがない場合は、「」を使用してください。foldl merge []'、そのほうが速いからです。

SQL の場合:

create table numbers(n int not null)
insert into numbers(n) values(1),(1), (2), (2), (3), (4)


select distinct num1.n+num2.n sum2n
from numbers num1
inner join numbers num2 
    on num1.n<>num2.n
order by sum2n

C# リンク:

List<int> num = new List<int>{ 1, 1, 2, 2, 3, 4};
var uNum = num.Distinct().ToList();
var sums=(from num1 in uNum
        from num2 in uNum 
        where num1!=num2
        select num1+num2).Distinct();
foreach (var s in sums)
{
    Console.WriteLine(s);
}

何をするにしても、入力値に追加の制約がなければ、O(n^2) よりも優れた結果を得ることができません。これは、数値のすべてのペアを反復処理する必要があるためです。反復はソートを支配します (ソートは O(n log n) 以上で実行できます)。

この質問はここ 1 日ほど私の頭を悩ませています。素晴らしい。

いずれにしても、n^2 の性質から簡単に抜け出すことはできませんが、マージを使用すると、各要素を挿入する範囲を制限できるため、多少は改善することができます。

生成したすべてのリストを見ると、次の形式になっています。

(a[i], a[j]) | j>=i

90度反転すると、次のようになります。

(a[i], a[j]) | i<=j

これで、マージプロセスは 2 つのリストを取得するはずです i そして i+1 (これは、最初のメンバーが常に a[i] そして a[i+1])、要素を挿入する範囲を制限できます (a[i + 1], a[j]) リストに入れる i の場所によって (a[i], a[j]) そしてその場所 (a[i + 1], a[j + 1]).

これは、次の点で逆にマージする必要があることを意味します。 j. 。これをさまざまな分野で活用できるかどうかは (まだ) わかりません j も可能ですが、可能だと思われます。

本当に言語に依存しないソリューションを探している場合は、for ループといくつかの条件文で行き詰まるため、私の意見では非常に失望するでしょう。ただし、関数型言語や関数型言語の機能 (LINQ を見ています) についてオープンにしている場合は、ここの同僚が Ruby、Lisp、Erlang などのエレガントな例でこのページを埋めることができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top