20

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

明確にするために、私はアルゴリズムに興味があります。好きな言語とパラダイムでコードを投稿してください。

4

8 に答える 8

12

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を選ぶ

もちろん、左上隅がたくさんある場合、このソリューションは発展します。

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

于 2008-09-18T21:41:13.387 に答える
4

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

最初のステップでは、長さ 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

マージ方法は、重複した合計がないことを確認するためのチェックを伴う通常のマージ手順になります。誰でもmergesortを調べることができるので、これは書きません。

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

于 2008-08-03T23:06:15.443 に答える
2

あなたはPythonで2行でこれを行うことができます

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

これのコストはn^2、反復の場合は（おそらくセットの追加の対数係数ですか？）、ソートの場合はs * log（s）です。ここで、sはセットのサイズです。

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

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

(n!)@ deuseldorf、Peter deuseldorfが「n階乗」を意味するのではなく、単に「n、（非常に興奮している）」という意味であると私が真剣に疑うことについて、いくつかの混乱があります。

于 2008-08-11T14:47:31.227 に答える
1

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

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 []より高速であるため、''を使用してください。

于 2008-08-03T21:36:25.890 に答える
1

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);
}
于 2008-08-08T23:05:47.057 に答える
1

この質問は、ここ 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、可能だと思われます。

于 2008-08-21T18:16:13.800 に答える
1

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

于 2008-09-18T22:15:18.577 に答える
-4

あなたが本当に言語にとらわれない解決策を探しているなら、あなたはforループといくつかの条件文で立ち往生するので、私の意見ではひどく失望するでしょう。ただし、関数型言語または関数型言語機能（LINQを見ています）を開いた場合、ここにいる私の同僚は、Ruby、Lisp、Erlangなどのエレガントな例でこのページを埋めることができます。

于 2008-08-03T21:24:56.160 に答える