خوارزمية لدمج المجموعات التي تشترك في عنصرين على الأقل

Question

نظرا لقائمة المجموعات:

• S_1 :[ 1، 2، 3، 4 ]
• S_2 :[ 3، 4، 5، 6، 7 ]
• س_3 :[ 8، 9، 10، 11 ]
• 4 س :[ 1، 8، 12، 13 ]
• س_5 :[ 6، 7، 14، 15، 16، 17 ]

ما هي الطريقة الأكثر فعالية لدمج جميع المجموعات التي تشترك في عنصرين على الأقل؟أفترض أن هذا مشابه لمشكلة المكونات المتصلة.وبالتالي ستكون النتيجة:

• [ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 يونيون S_2 يونيون S_5)
• [ 8, 9, 10, 11 ]
• [ 1, 8, 12, 13 ] (S_4 يشترك في 1 مع S_1، و8 مع S_3، ولكن لم يتم دمجهما لأنهما يشتركان في عنصر واحد فقط في كل منهما)

التنفيذ الساذج هو O(N^2)، حيث N هو عدد المجموعات، وهو أمر غير عملي بالنسبة لنا.يجب أن يكون هذا فعالاً لملايين المجموعات.

Answer 1

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

رأسي يقول أن هذا يتعلق بالأمر (2N ln N).خذ ذلك مع حبة الملح.

Answer 2

إذا كان بإمكانك طلب العناصر الموجودة في المجموعة، فيمكنك النظر في استخدامها فرز الدمج على المجموعات.التعديل الوحيد المطلوب هو التحقق من التكرارات أثناء مرحلة الدمج.إذا تم العثور على واحدة، فما عليك سوى تجاهل النسخة المكررة.نظرًا لأن عملية فرز الدمج هي O(n*log(n)))، فإن هذا سيوفر سرعة محسنة عند مقارنتها بخوارزمية O(n^2) الساذجة.

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

Answer 3

لا أرى كيف يمكن القيام بذلك في أقل من O(n^2).

يجب مقارنة كل مجموعة مع بعضها البعض لمعرفة ما إذا كانت تحتوي على عنصرين مشتركين أو أكثر.هذه هي مقارنات n*(n-1)/2، وبالتالي O(n^2)، حتى لو كان التحقق من العناصر المشتركة يستغرق وقتًا ثابتًا.

في الفرز، يكون التنفيذ الساذج هو O(n^2) ولكن يمكنك الاستفادة من الطبيعة المتعدية للمقارنة المرتبة (لذلك، على سبيل المثال، لا تعرف شيئًا في القسم السفلي من الفرز السريع يحتاج إلى مقارنته بأي شيء في القسم العلوي ، حيث تمت مقارنتها بالفعل بالمحور).وهذا ما يؤدي إلى أن يكون الفرز O(n * log n).

هذا لا ينطبق هنا.لذلك ما لم يكن هناك شيء خاص حول المجموعات يسمح لنا بتخطي المقارنات بناءً على نتائج المقارنات السابقة، فسيكون O(n^2) بشكل عام.

بول.

Answer 4

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

Answer 5

إذا كانت عناصرك ذات طبيعة عددية، أو يمكن ترتيبها بشكل طبيعي (على سبيل المثال.يمكنك تعيين قيمة مثل 1، 2، 42، إلخ...)، أقترح استخدام فرز جذري للمجموعات المدمجة، وإجراء تمريرة ثانية لالتقاط العناصر الفريدة.

يجب أن تكون هذه الخوارزمية من النوع O(n)، ويمكنك تحسين فرز الجذر قليلاً باستخدام عوامل تحويل البت وأقنعة البت.لقد قمت بشيء مماثل لمشروع كنت أعمل عليه، وهو يعمل كالسحر.