الحصول على مبالغ مرتبة من قائمة مرتبة بكفاءة

Question

لديك قائمة تصاعدية من الأرقام، ما هي الخوارزمية الأكثر كفاءة التي يمكنك التفكير فيها للحصول على قائمة تصاعدية لمجموع كل رقمين في تلك القائمة.التكرارات في القائمة الناتجة ليست ذات صلة، يمكنك إزالتها أو تجنبها إذا أردت.

لأكون واضحًا، أنا مهتم بالخوارزمية.لا تتردد في نشر الكود بأي لغة ونموذج تريده.

Answer 1

التعديل اعتبارًا من 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]، فإنك تحتاج فقط إلى فحص الجزء العلوي الأيسر " الزوايا" واختر الأقل.

على سبيل المثال

• زاوية واحدة فقط في الزاوية اليسرى العليا، اختر 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] - ما لم يكن لدى شخص ما خوارزمية أفضل للجمع :)

Answer 2

بدلاً من ترميز ذلك، أعتقد أنني سأقوم بتشفيره بشكل زائف في خطوات وشرح المنطق الخاص بي، حتى يتمكن المبرمجون الأفضل من إحداث ثغرات في المنطق الخاص بي إذا لزم الأمر.

في الخطوة الأولى نبدأ بقائمة من الأرقام بطول n.لكل رقم نحتاج إلى إنشاء قائمة بطول n-1 لأننا لا نضيف رقمًا إلى نفسه.في النهاية لدينا قائمة تضم حوالي 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، نظرًا لأن القوائم تم فرزها حسب التصميم (أضف رقمًا إلى كل عنصر في قائمة مفروزة وستظل القائمة مرتبة)، يمكننا ببساطة إجراء فرز مدمج عن طريق دمج كل قائمة معًا بدلاً من دمج فرز المجموعة بأكملها.في النهاية، يجب أن يستغرق هذا وقتًا 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) الوقت.لا تتردد في الإشارة إلى أي أخطاء أو تحسينات.

Answer 3

يمكنك القيام بذلك في سطرين في بايثون باستخدام

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 على الأقل في أسوأ الحالات نظرًا لأن هذا هو حجم الإخراج.

ومع ذلك، إذا كنت تريد تحديد العناصر k الأولى من النتيجة، فيمكنك القيام بذلك في O(kn) باستخدام خوارزمية تحديد لمصفوفات X+Y التي تم فرزها بواسطة Frederickson وJohnson (انظر هنا للحصول على تفاصيل دموية).على الرغم من أنه من الممكن تعديل هذا لإنشاءها عبر الإنترنت عن طريق إعادة استخدام الحساب والحصول على مولد فعال لهذه المجموعة.

deuseldorf ، بيتر هناك بعض الالتباس حول (n!) أنا أشك بجدية في Deuseldorf يعني "n factorial" ولكن ببساطة "n ، (متحمس للغاية)!"

Answer 4

أفضل ما يمكنني التوصل إليه هو إنتاج مصفوفة من مجموع كل زوج، ثم دمج الصفوف معًا، بطريقة الدمج.أشعر وكأنني أفتقد بعض الأفكار البسيطة التي ستكشف عن حل أكثر كفاءة.

الخوارزمية الخاصة بي في هاسكل:

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 []"، لأنه أسرع.

Answer 5

في 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);
}

Answer 6

بغض النظر عما تفعله، بدون قيود إضافية على قيم الإدخال، لا يمكنك القيام بعمل أفضل من O(n^2)، وذلك ببساطة لأنه يتعين عليك التكرار عبر جميع أزواج الأرقام.سيهيمن التكرار على عملية الفرز (وهو ما يمكنك القيام به في O(n log n) أو بشكل أسرع).

Answer 7

لقد ظل هذا السؤال يدمر ذهني منذ يوم تقريبًا.مذهل.

على أي حال، لا يمكنك الابتعاد عن طبيعة 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 كذلك، ولكن يبدو أنه من الممكن.

Answer 8

إذا كنت تبحث عن حل لا يتقن اللغة حقًا، فسوف تشعر بخيبة أمل شديدة في رأيي لأنك ستظل عالقًا في حلقة for وبعض الشروط.ومع ذلك، إذا فتحت الأمر للغات الوظيفية أو ميزات اللغة الوظيفية (أنا أنظر إليك LINQ)، فيمكن لزملائي هنا ملء هذه الصفحة بأمثلة أنيقة في Ruby وLisp وErlang وغيرها.