Αποτελεσματική πάρει ταξινομημένο ποσά της ταξινομημένη λίστα

ψήφοι
17

Έχετε μια λίστα με αύξουσα αριθμούς, αυτό είναι το πιο αποτελεσματικό αλγόριθμο που μπορείτε να σκεφτείτε για να πάρετε τον κατάλογο αύξουσα των ποσών των κάθε δύο αριθμούς στον εν λόγω κατάλογο. Αντίγραφα στη λίστα που προκύπτει είναι άσχετη, μπορείτε να τα αφαιρέσετε ή να τις αποφύγετε, αν θέλετε.

Για να είμαι σαφής, είμαι ενδιαφέρονται για τον αλγόριθμο. Μη διστάσετε να δημοσιεύσετε κώδικα σε οποιαδήποτε γλώσσα και μοντέλο που σας αρέσει.

Δημοσιεύθηκε 03/08/2008 στις 22:08
πηγή χρήστη
Σε άλλες γλώσσες...                            


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

Θα παρατηρήσετε ότι από το Μ [i, j] <= Μ [i, j + 1] και Μ [i, j] <= Μ [i + 1, j], τότε το μόνο που χρειάζεται για να εξετάσει το πάνω αριστερά " γωνίες»και επιλέξτε το χαμηλότερο μία.

π.χ

  • μόνο 1 επάνω αριστερή γωνία, επιλέξτε 2
  • μόνο 1, πάρτε 5
  • 6 ή 8, pick 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] - εκτός αν κάποιος έχει ένα καλύτερο αλγόριθμο για το άθροισμα :)

Απαντήθηκε 18/09/2008 στις 22:41
πηγή χρήστη

ψήφοι
4

Αντί κωδικοποίησης αυτό έξω, μπορώ να καταλάβω εγώ θα ψευδο-κώδικας είναι σε βήματα και να εξηγήσει τη λογική μου, έτσι ώστε καλύτερη προγραμματιστές μπορούν να σακί τρύπες στην λογική μου, αν είναι απαραίτητο.

Στο πρώτο βήμα που ξεκινούν με μια λίστα μήκους αριθμούς n. Για κάθε αριθμό πρέπει να δημιουργήσουμε μια λίστα μήκους n-1 becuase δεν είμαστε προσθήκη ενός αριθμού στον εαυτό του. Μέχρι το τέλος έχουμε μια λίστα με περίπου n ταξινομημένο καταλόγους που δημιουργήθηκε σε O (n ^ 2) το χρόνο.

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, διότι οι κατάλογοι έχουν ταξινομηθεί από τον σχεδιασμό (προσθέσετε έναν αριθμό σε κάθε στοιχείο σε μια ταξινομημένη λίστα και η λίστα θα εξακολουθεί να ταξινομηθούν) μπορούμε απλά να κάνουμε μια συγχωνευτική με τη συγχώνευση ο ένας τον κατάλογο μαζί και όχι mergesorting το σύνολο της παρτίδας. Στο τέλος αυτό θα πρέπει να λάβει 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) το χρόνο. Μη διστάσετε να επισημάνει τυχόν λάθη ή βελτιώσεις.

Απαντήθηκε 04/08/2008 στις 00:06
πηγή χρήστη

ψήφοι
2

Μπορείτε να το κάνετε αυτό σε δύο γραμμές σε python με

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 για παράδειγμα, αν το Χ = [1,2,4, ..., 2 ^ n]. Έτσι, εάν θέλετε να δημιουργήσετε αυτή τη λίστα θα χρειαστούν τουλάχιστον n ^ 2/2 στη χειρότερη περίπτωση, δεδομένου ότι αυτό είναι το μέγεθος της εξόδου.

Ωστόσο, εάν θέλετε να επιλέξετε τα πρώτα k στοιχεία για το αποτέλεσμα μπορείτε να το κάνετε αυτό σε O (kn) χρησιμοποιώντας έναν αλγόριθμο επιλογής για ταξινόμηση πίνακες X + Y από Φρέντρικσον και Johnson ( δείτε εδώ για φρικιαστικές λεπτομέρειες) . Αν και αυτό μπορεί πιθανόν να τροποποιηθεί για τη δημιουργία τους σε απευθείας σύνδεση με την επαναχρησιμοποίηση υπολογισμούς και να πάρετε μια αποδοτική γεννήτρια για αυτό το σύνολο.

@deuseldorf, Peter Υπάρχει κάποια σύγχυση σχετικά με (n!) Έχω σοβαρές αμφιβολίες deuseldorf σημαίνει «η παραγοντική», αλλά απλά «n, (πολύ ενθουσιασμένοι)!»

Απαντήθηκε 11/08/2008 στις 15:47
πηγή χρήστη

ψήφοι
1

Δεν έχει σημασία τι θα κάνεις, χωρίς πρόσθετους περιορισμούς σχετικά με τις τιμές εισόδου, δεν μπορείτε να κάνετε καλύτερα από O (n ^ 2), μόνο και μόνο επειδή θα πρέπει να επαναλαμβάνεται σε όλα τα ζεύγη των αριθμών. Η επανάληψη θα κυριαρχήσουν διαλογής (το οποίο μπορείτε να κάνετε σε O (n log n) ή πιο γρήγορα).

Απαντήθηκε 18/09/2008 στις 23:15
πηγή χρήστη

ψήφοι
1

Αυτή η ερώτηση έχει wracking μυαλό μου για περίπου μια μέρα τώρα. Φοβερός.

Anyways, δεν μπορεί να περάσει από το n ^ 2 η φύση της είναι εύκολα, αλλά μπορείτε να το κάνετε λίγο καλύτερα με τη συγχώνευση δεδομένου ότι μπορείτε να δεσμεύεται το εύρος για να εισάγετε κάθε στοιχείο του.

Αν κοιτάξετε όλες τις λίστες που παράγουν, έχουν την ακόλουθη μορφή:

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

Αν το κτύπημα 90 μοίρες, μπορείτε να πάρετε:

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

Τώρα, η διαδικασία συγχώνευσης θα πρέπει να λαμβάνουν δύο λίστες 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καθώς επίσης, αλλά φαίνεται πιθανή.

Απαντήθηκε 21/08/2008 στις 19:16
πηγή χρήστη

ψήφοι
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 # 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);
}
Απαντήθηκε 09/08/2008 στις 00:05
πηγή χρήστη

ψήφοι
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 []», όπως είναι πιο γρήγορο.

Απαντήθηκε 03/08/2008 στις 22:36
πηγή χρήστη

ψήφοι
-4

Αν ψάχνετε για μια πραγματικά γλώσσα αγνωστικιστής λύση, τότε θα είναι βαθιά απογοήτευση κατά τη γνώμη μου, γιατί θα πρέπει να κολλήσει με ένα for loop και μερικές υποθετικοί. Ωστόσο, εάν το άνοιγμα των λειτουργικών γλώσσες ή λειτουργικά χαρακτηριστικά γλώσσας (είμαι σε κοιτάζω LINQ), τότε οι συνάδελφοί μου εδώ μπορεί να γεμίσει αυτή τη σελίδα με κομψή παραδείγματα σε Ruby, Lisp, Erlang, και άλλα.

Απαντήθηκε 03/08/2008 στις 22:24
πηγή χρήστη

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