الدمج خطوة بخطوة

جزء من قسم التعلّم غير الخاضع للإشراف في رحلة Machine Learning على Coddy. الدرس 16 من 51.

ينشئ هذا الفصل شجرة عائلة لبياناتك، ثم يقسمها إلى مجموعات. إليك عشر كرات رياضية، بحسب الحجم والوزن:

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

تنمو الشجرة من الأسفل إلى الأعلى. ابدأ بكل نقطة منفردة، ثم ادمج أقرب مجموعتين، وكرّر:

خمسة خيام على امتداد نهر عند 2 و7 و15 و19 و33 مترًا، مرسومة في خمسة صفوف. في الخطوة 1 يُدمج 15 و19، وفي الخطوة 2 يُدمج 2 و7، وفي الخطوة 3 تُجمع هاتان المجموعتان، وفي الخطوة 4 تُضاف 33

الفجوة بين مجموعتين هي الفجوة بين متوسطيهما. الدمج، كما في القوائم:

groups = [[2], [7], [15, 19], [33]]
groups[0] = groups[0] + groups[1]  # ادمج القوائم
groups.pop(1)  # أزل [7]، فهي الآن في المجموعة 0
print(groups)

يطبع هذا [[2, 7], [15, 19], [33]]. دمجًا تلو الآخر، وهذا هو التجميع التجميعي.

التحدي

متوسط

تزرع العائلات مظلات الشاطئ متقاربة. اجمع المظلات العشر في spots عن طريق الدمج، حتى يتبقى wanted مجموعات. تُرجع closest_pair(groups) موضعي i وj للمجموعتين الأقرب.

ابدأ بكل مظلة وحدها، في قائمة من عنصر واحد.
ما دامت هناك مجموعات أكثر من wanted: اطبع عملية الدمج، واجمع الزوج، واحذف المجموعة الثانية.
اطبع المجموعات المتبقية.

بالنسبة إلى المظلات الأخرى وwanted تساوي 3:

Merge [33] and [35]
Merge [30] and [33, 35]
Merge [3] and [8]
3 groups: [[3, 8], [30, 33, 35], [70]]

جرّب بنفسك

import numpy as np

# مواقع 10 مظلات شاطئية، بالأمتار من برج المنقذ
spots = [2, 9, 11, 31, 45, 46, 69, 74, 92, 96]


# تُرجع i وj (i < j): موضعي المجموعتين اللتين متوسطاهما الأقرب إلى بعضهما
def closest_pair(groups):
    best_i, best_j = 0, 1
    best_gap = abs(np.mean(groups[0]) - np.mean(groups[1]))
    for i in range(len(groups)):
        for j in range(i + 1, len(groups)):
            gap = abs(np.mean(groups[i]) - np.mean(groups[j]))
            if gap < best_gap:
                best_i, best_j, best_gap = i, j, gap
    return best_i, best_j


wanted = int(input())

# اكتب الكود الخاص بك أدناه