Hiệu quả nhận được các khoản được sắp xếp của một danh sách được sắp xếp

Question

Bạn có một danh sách các số tăng dần, thuật toán hiệu quả nhất mà bạn có thể nghĩ là có được danh sách tổng của hai số trong danh sách tăng dần. Các bản sao trong danh sách kết quả không liên quan, bạn có thể xóa chúng hoặc tránh chúng nếu bạn muốn.

Để rõ ràng, tôi quan tâm đến thuật toán. Vui lòng đăng mã bằng bất kỳ ngôn ngữ và mô hình nào mà bạn thích.

Answer 1

Chỉnh sửa từ năm 2018: Có thể bạn nên ngừng đọc nội dung này. (Nhưng tôi không thể xóa nó vì nó được chấp nhận.)

Nếu bạn viết ra số tiền như thế này:

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 

Bạn sẽ nhận thấy rằng kể từ M [i, j] < = M [ i, j + 1] và M [i, j] < = M [i + 1, j], thì bạn chỉ cần kiểm tra "góc" trên cùng bên trái và chọn điểm thấp nhất.

ví dụ:

• chỉ có 1 góc trên bên trái, chọn 2
• chỉ có 1, chọn 5
• 6 hoặc 8, chọn 6
• 7 hoặc 8, chọn 7
• 9 hoặc 8, chọn 8
• 9 hoặc 9, chọn cả hai :)
• 10 hoặc 10 hoặc 10, chọn tất cả
• 12 hoặc 11, chọn 11
• 12 hoặc 12, chọn cả hai
• 13 hoặc 13, chọn cả hai
• 14 hoặc 14, chọn cả hai
• 15 hoặc 16, chọn 15
• chỉ có 1, chọn 16
• chỉ có 1, chọn 17
• chỉ có 1, chọn 18

Tất nhiên, khi bạn có nhiều góc trên bên trái sau đó giải pháp này mạn.

Tôi chắc rằng vấn đề này là Ω (n ²), bởi vì bạn phải tính toán số tiền cho mỗi M [i, j] - trừ khi ai đó có một thuật toán tốt hơn cho tổng :)

Answer 2

Nếu bạn đang tìm kiếm một giải pháp bất khả tri về ngôn ngữ thực sự thì bạn sẽ vô cùng thất vọng trong quan điểm của tôi vì bạn sẽ bị mắc kẹt với vòng lặp for và một số điều kiện. Tuy nhiên, nếu bạn mở nó lên các ngôn ngữ chức năng hoặc các tính năng ngôn ngữ chức năng (tôi đang nhìn vào bạn LINQ) thì các đồng nghiệp của tôi ở đây có thể điền vào trang này với các ví dụ thanh lịch trong Ruby, Lisp, Erlang và các ngôn ngữ khác.

Answer 3

Điều tốt nhất tôi có thể đưa ra là tạo ra một ma trận tổng của mỗi cặp, sau đó hợp nhất các hàng với nhau, sắp xếp hợp nhất a-la. Tôi cảm thấy như tôi đang thiếu một số hiểu biết đơn giản mà sẽ tiết lộ một giải pháp hiệu quả hơn nhiều.

thuật toán của tôi, trong 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) 

Tôi tìm thấy một sự cải thiện đáng kể, một trong đó là dễ dàng cho lười biếng mã hóa dựa trên luồng. Thay vì hợp nhất các cột một cách khôn ngoan, hãy hợp nhất tất cả các cột cùng một lúc. Lợi thế là bạn bắt đầu nhận được các yếu tố của danh sách ngay lập tức.

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

Tuy nhiên, nếu bạn biết bạn đang đi để sử dụng tất cả các khoản tiền, và không có lợi thế để nhận được một số trong số họ trước đó, đi với 'foldl merge []', vì nó nhanh hơn.

Answer 4

Thay vì viết mã này ra, tôi hình tôi sẽ giả mã nó theo các bước và giải thích logic của tôi, để các lập trình viên tốt hơn có thể chọc lỗ trong logic của tôi nếu cần.

Trong bước đầu tiên, chúng tôi bắt đầu với một danh sách các số có độ dài n. Đối với mỗi số chúng ta cần tạo một danh sách độ dài n-1 vì chúng ta không thêm một số vào chính nó. Cuối cùng chúng ta có một danh sách về n danh sách được sắp xếp đã được tạo ra trong thời gian 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 

Trong bước 2 vì danh sách được sắp xếp theo thiết kế (thêm một số cho mỗi phần tử trong danh sách được sắp xếp và danh sách vẫn sẽ được sắp xếp), chúng tôi chỉ có thể làm một mergesort bằng cách sáp nhập mỗi danh sách với nhau hơn là mergesorting cả lô. Cuối cùng điều này sẽ mất thời gian 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 

Phương pháp hợp nhất sẽ là bước hợp nhất bình thường với séc để đảm bảo không có khoản tiền trùng lặp. Tôi sẽ không viết điều này ra bởi vì bất cứ ai cũng có thể tra cứu hợp nhất.

Vì vậy, có giải pháp của tôi. Toàn bộ thuật toán là thời gian O (n^2). Vui lòng chỉ ra bất kỳ sai lầm hoặc cải tiến nào.

Answer 5

Trong 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); 
} 

Answer 6

Bạn có thể làm điều này trong hai dòng trong python với

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

Chi phí của việc này là n^2 (có thể là một yếu tố đăng nhập bổ sung cho tập hợp?) cho phép lặp và s * log (s) cho việc sắp xếp trong đó s là kích thước của tập hợp.

Kích thước của tập hợp có thể lớn bằng n * (n-1)/2 ví dụ nếu X = [1,2,4, ..., 2^n]. Vì vậy, nếu bạn muốn tạo danh sách này, nó sẽ mất ít nhất n^2/2 trong trường hợp xấu nhất vì đây là kích thước của đầu ra.

Tuy nhiên nếu bạn muốn chọn phần tử k đầu tiên của kết quả, bạn có thể thực hiện điều này bằng O (kn) bằng thuật toán lựa chọn cho ma trận X + Y được sắp xếp bởi Frederickson và Johnson (see here for gory details)). tạo ra chúng trực tuyến bằng cách sử dụng lại tính toán và nhận được một máy phát điện hiệu quả cho bộ này.

@deuseldorf, Peter Có một số nhầm lẫn về (n!) Tôi nghi ngờ nghiêm trọng deuseldorf có nghĩa là "n giai thừa" nhưng đơn giản là "n, (rất vui mừng)! "

Answer 7

Câu hỏi này đã bẻ khóa não của tôi trong khoảng một ngày nay. Tuyệt vời.

Dù sao, bạn không thể thoát khỏi bản chất n^2 dễ dàng, nhưng bạn có thể làm tốt hơn một chút với việc hợp nhất vì bạn có thể giới hạn phạm vi để chèn từng phần tử vào.

Nếu bạn nhìn vào tất cả danh sách mà bạn tạo ra, họ có các hình thức sau đây:

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

Nếu bạn lật nó 90 độ, bạn sẽ có được:

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

Bây giờ, t ông hợp nhất quy trình nên dùng hai danh sách i và i+1 (tương ứng với danh sách mà các thành viên đầu tiên luôn luôn là a[i] và a[i+1]), bạn có thể bị ràng buộc phạm vi để chèn yếu tố (a[i + 1], a[j]) vào danh sách i bởi vị trí của (a[i], a[j]) và vị trí của (a[i + 1], a[j + 1]).

Điều này có nghĩa là bạn nên hợp nhất ngược lại theo số j. Tôi không biết (chưa) nếu bạn có thể tận dụng điều này trên j là tốt, nhưng có vẻ như có thể.

Answer 8

Không vấn đề bạn làm, không có ràng buộc bổ sung về giá trị đầu vào, bạn không thể làm tốt hơn O (n^2), đơn giản chỉ vì bạn phải lặp qua tất cả các cặp số. Việc lặp lại sẽ thống trị phân loại (mà bạn có thể làm trong O (n log n) hoặc nhanh hơn).