Účinně dostat setříděné sumy seřazeném seznamu

hlasů
17

Máte vzestupný seznam čísel, co je nejefektivnější algoritmus si můžete myslet získat vzestupný seznam částek každých dvou čísel v tomto seznamu. Duplikáty ve výsledném seznamu jsou irelevantní, můžete je odstranit, nebo se jim vyhnout, pokud se vám líbí.

Aby bylo jasno, já jsem zájem o algoritmu. Neváhejte post kód v jakémkoli jazyce a paradigma, které se vám líbí.

Položena 03/08/2008 v 22:08
zdroj uživatelem
V jiných jazycích...                            


8 odpovědí

hlasů
12

Editovat as of 2018: Pravděpodobně byste měli přestat číst tento. (Ale nemůžu ho odstranit, protože je přijat.)

Máte-li vypsat částky, jako je tento:

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

Všimněte si, že od té doby M [i, j] <= M [i, j + 1] a M [i, j] <= M [i + 1, j], pak je třeba jen zkoumat vlevo nahoře " rohy“a vybrat ten nejnižší.

např

  • Pouze 1 levý horní roh, vybrat 2
  • pouze 1, pick 5
  • 6 nebo 8, vybrat 6
  • 7 nebo 8, vybrat 7
  • 9 nebo 8, vybrat 8
  • 9 nebo 9, a to jak vybrat :)
  • 10 nebo 10 nebo 10, vybrat vše
  • 12 nebo 11, vybrat 11
  • 12 nebo 12, jak vybrat
  • 13 nebo 13, jak vybrat
  • 14 nebo 14, jak vybrat
  • 15 nebo 16, vybrat 15
  • pouze 1, pick 16
  • pouze 1, pick 17
  • pouze 1, pick 18

Samozřejmě, když máte spoustu z horního rohu pak toto řešení přejde.

Jsem si docela jistý, že tento problém je Ω (n?), Protože musíte počítat částky za každý M [i, j] - pokud někdo má lepší algoritmus pro sčítání :)

Odpovězeno 18/09/2008 v 22:41
zdroj uživatelem

hlasů
4

Spíše než toto kódování out, Hádám budu pseudo-kód je v krocích a vysvětlit svou logiku, takže lepší programátoři mohou hrabat díry v mé logice v případě potřeby.

Na prvním stupni začneme se seznamem čísel délky n. U každého čísla je třeba vytvořit seznam délky n-1 becuase nejsme přidávání čísel do sebe. Na konci máme seznam o n seřazeny seznam, který byl vytvořen v O (n ^ 2) času.

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 

V kroku 2, protože tyto seznamy byly seřazeny podle návrhu (přidat číslo do každého prvku v seřazeném seznamu a bude i nadále řazeny seznam) můžeme jednoduše udělat mergesort sloučením každého seznamu spolu spíše než mergesorting celý pozemek. Nakonec by to mělo trvat O čas (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

Metoda sloučení by pak normální sloučení krok s kontrolou, aby se ujistil, že neexistují žádné duplicitní částky. Nebudu psát na to proto, že každý může podívat do mergesort.

Takže tady je moje řešení. Celý algoritmus je O (n ^ 2) času. Neváhejte a poukázat na chyby nebo vylepšení.

Odpovězeno 04/08/2008 v 00:06
zdroj uživatelem

hlasů
2

To lze provést ve dvou řadách v Pythonu s

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

Náklady na to je n ^ 2 (možná extra log faktor pro natáčení?) Pro opakování a y * log (y) pro třídění, kde s je velikost sady.

Velikost souboru může být tak velký, jako je n * (n-1) / 2 například, pokud X = [1,2,4, ..., 2 ^ n]. Takže pokud chcete vytvořit tento seznam bude trvat nejméně n ^ 2/2 v nejhorším případě, protože to je velikost výstupu.

Nicméně, chcete-li zvolit první K prvky výsledku můžete to udělat v O (kN) za použití výběrový algoritmus pro seřazených X + Y matrice podle Frederickson a Johnson ( viz zde krvavé podrobnosti) . Přestože to může být pravděpodobně upraven tak, aby jim vytvářet online opětovné výpočty a získat efektivní generátor pro tuto skupinu.

@deuseldorf, Peter Tam je nějaký zmatek ohledně (n!) jsem vážně pochybovat deuseldorf znamenalo „n faktoriál“, ale pouze „n, (velmi rádi)!“

Odpovězeno 11/08/2008 v 15:47
zdroj uživatelem

hlasů
1

Bez ohledu na to, co děláte, a to bez dalších podmínek na vstupních hodnot, můžete to udělat lépe, než O (n ^ 2), prostě proto, že jste iterovat všechny dvojice čísel. Iterace bude dominovat třídění (které můžete udělat v O (n log n) nebo rychlejší).

Odpovězeno 18/09/2008 v 23:15
zdroj uživatelem

hlasů
1

Tato otázka byla drásající můj mozek asi den teď. Úžasný.

Tak jako tak, nemůžete dostat pryč od n ^ 2 povaze to snadno, ale můžete to udělat o něco lépe s sloučení, protože můžete vázán rozsah vložit každý prvek.

Když se podíváte na všechny seznamy generovaných, mají následující podobu:

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

Pokud jej otočit o 90 stupňů, získáte:

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

Nyní procesu sloučení by mělo brát dva seznamy ia i+1(což koresponduje s seznamy, kde první člen je vždy a[i]a a[i+1]), můžete vázán na řadu vložit prvek (a[i + 1], a[j])do seznamu ipodle umístění (a[i], a[j])a umístění (a[i + 1], a[j + 1]).

To znamená, že byste měli sloučit v opačném směru, pokud jde o j. Já nevím (zatím), pokud mohou využít tento napříč jstejně, ale zdá se, je to možné.

Odpovězeno 21/08/2008 v 19:16
zdroj uživatelem

hlasů
1

V 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 # LINQ:

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);
}
Odpovězeno 09/08/2008 v 00:05
zdroj uživatelem

hlasů
1

Nejlepší, co jsem mohl přijít s je vytvořit matici částek každého páru, a pak sloučit řádky dohromady, a-la merge sort. Mám pocit, že mi chybí nějaký jednoduchý pohled, který odhalí mnohem účinnější řešení.

Můj algoritmus, v 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)

Zjistil jsem, menší zlepšení, ten, který je vhodnější pro líné kódování proudu na bázi. Namísto slučování sloupce párový, sloučit všechny najednou. Výhodou je, že začnete okamžitě dostat prvky seznamu.

-- 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

Nicméně, pokud víte, že budete používat všechny částky, a tam žádná výhoda k získání některé z nich dříve, jít s ‚ foldl merge []‘, protože je to rychlejší.

Odpovězeno 03/08/2008 v 22:36
zdroj uživatelem

hlasů
-4

Pokud hledáte pro skutečně jazyka agnostik řešení pak budete velice zklamaný podle mého názoru, protože budete na krku smyčku for a některé conditionals. Nicméně, pokud si ji otevřel až funkcionálních jazyků nebo funkčních jazykových prvků (Dívám se na tebe LINQ), pak moji kolegové zde mohou vyplnit tuto stránku s elegantním příklady v Ruby, Lisp, Erlang, a jiní.

Odpovězeno 03/08/2008 v 22:24
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more