الاتحاد لجميع مجموعات التقاطع

Question

بالنظر إلى قائمة الكائنات التي تحتوي على سمات متعددة أحتاج إلى العثور على قائمة المجموعات التي تم إنشاؤها بواسطة اتحاد جميع مجموعات فرعية تقاطع.

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

على سبيل المثال، إذا كان الشخص A وشخصي B لديه نفس SSN يقومون بإنشاء مجموعة I. ثم إذا كان الشخص B و C لديه نفس DLN، فإنها تنشئ مجموعة II. الأشخاص D و E لديهم نفس SSN لكنه (وجميع المعرفات الأخرى) لا يتطابق مع أي من معرفات الأشخاص A أو B أو C. بعد دمج جميع مجموعات فرعية تقاطعية وأود أن ينتهي بهم المطاف مع مجموعة واحدة مع أشخاص A، B، C ومجموعة أخرى مع أشخاص د، هاء

هنا هو رمز psuedo لحل بلدي. أنا فضولي إذا كان أي شخص قد وصل بالفعل بطريقة أكثر كفاءة لدمج جميع مجموعات التقاطع الممكنة. ضع في اعتبارك أن الروابط بين مجموعات يمكن أن تكون X أشخاص طويلة (أي مباريات ب بواسطة SSN و B Citters C By DLN و C يطابق D By SSN و D يتطابق E بواسطة بعض المعرف الآخر سيؤدي إلى أشخاص آخرين في مجموعة واحدة). افترض أيضا أن اللغة سيتم تنفيذها في عمليات دعم العمليات.

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end

Answer 1

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

بما سذري، يمكن حل ذلك إما عن طريق العثور على جميع الأزواج التي تشترك في سمة ودمج أزواج معا التي لها نفس الشريك بالتكرار. سيكون هذا س (n ^ 3) (n ^ 2 للتكرار فوق أزواج، وحتى N منفصلة مجموعات لتحديد العضوية).

يمكنك أيضا التفكير في هذه المشكلة مثل تحديد مكون متصل بياني, حيث كل كائن وكل قيمة سمة فريدة هي عقدة؛ سيتم توصيل كل كائن بكل قيم سمة. سيؤدي إعداد هذا الرسم البياني إلى وقت خطي، ويمكنك تحديد المكونات المتصلة في الوقت الخطي مع عملية البحث أو العمق الأول.

Answer 2

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

Answer 3

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

Answer 4

أولا، هل هناك بعض التسلسل الهرمي الكامن في المعرفات، وتتناقض مع معرفات من نوع أعلى إلغاء الهوية نفس المعرف لسلفة أقل؟ على سبيل المثال، إذا كان لدى A و B نفس SSN، فإن B و C لديها نفس DLN، و C و D Have نفس SSN الذي لا يتطابق مع SSN A و B، هل يعني أن هناك مجموعتان أو واحد؟

لا يهم بافتراض التناقضات، فأنت تتعامل مع فصول التكافؤ، كدولة 57368 (جوجل غير معروفة). بالنسبة لفصول التكافؤ، غالبا ما يتحول الناس إلى union-find. هيكل. أما بالنسبة لكيفية تنفيذ هذه النقابات، فهي ليست تافهة على الفور لأنني أفترض أنك لا تملك الرابط المباشر AB عندما يكون لدى كل من A و B نفس SSN. بدلا من ذلك، ستتألف مجموعاتنا من نوعين من العناصر. كل (attribute type, attribute value) = attribute الزوج هو عنصر. لديك أيضا عناصر المقابلة objectس. عند التكرار من خلال قائمة السمات لكائن، قم بإجراء النقابة (object, attribute).

تتمثل إحدى الميزات المهمة بنية البيانات في Union-Find بنية البيانات في أن الهيكل الناتج يمثل المجموعة. يتيح لك الاستعلام عن "ما المجموعة"؟ إذا لم يكن هذا كافيا، فأخبرنا بذلك ويمكننا تحسين النتيجة.

لكن الميزة الأكثر أهمية هي أن الخوارزمية لديها شيء يشبه السلوك المستمر لكل عملية اتحاد واستعلام.

Answer 5

لذلك يمكن أن تبدو مثال جمعك مثل هذا:

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

ثم أود أن أقترح استخدام خوارزمية حيث يمكنك بناء مجموعات متعددة من خلال دمج أو إدراج كل مجموعة تدريجيا في المجموعات المتعددة:

التكرار 1. تصبح المجموعة الأولى هي المجموعة الوحيدة متعددة:

{A} { ss |-> [42], dl |-> [123] }

التكرار 2. دمج المجموعة التالية في الأول منذ SSN موجود بالفعل:

{A,B} { ss |-> [42], dl |-> [123,456] }

التكرار 3. دمج مرة أخرى، لأن DLN موجود بالفعل:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

التكرار 4. إدراج مجموعة متعددة جديدة نظرا لعدم وجود تطابق:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

التكرار 5. دمج مع مجموعة ثانية متعددة، لأن SSN هناك:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

لذلك في كل تكرار (واحد لكل مجموعة)، يجب عليك تحديد الكل متعدد المجموعات التي لها قيم مشتركة مع المجموعة التي تجريها، ودمج الكل هذه معا.

بشكل عام، إذا كانت هناك مجموعات N مع عدد من السمات K ثابت، فسيتم تشغيل هذه الخوارزمية في الوقت المناسب (NNK) = O (N²). يتم خلع سلوك الأحرف الأسوأ إذا كانت جميع قيم السمة مميزة. عندما يكون هناك المزيد من التقاسم بين قيم السمة، يحصل الوقت الذي يستغرقه إدراج وتحديد العضوية في مجموعات قيمة السمة (مثل [23،42]) هو العامل المهيمن، لذلك يجب أن تكون مجموعات قيمة السمات فعالة.

كما ترى مجموعات فكين الأمثل, ، ثم سيتم تشغيل كل عملية تجد أو دمج في وقت إطفاء O (α (n)).

وبالتالي، بالنسبة لكل تكرار سيكون هناك في معظم مجموعات N متعددة (الوضع عندما تم دمج أي مجموعات متعددة حتى الآن). لدمج المجموعة الجديدة في المجموعات المتعددة، سيتعين عليك تنفيذ عملية تجد على كل مجموعات من مجموعات K متعددة المجموعات لتحديد جميع المجموعات المتعددة التي سيتم دمجها، والتي تستغرق وقتا طويلا من قبل O (NKα (N)) وبعد لدمج في معظم مجموعات K متعددة المجموعات وجدت بهذه الطريقة تأخذ O (K²α (ن)).

لذلك لجميع التكرار يحد الوقت O (N (NKα (N) + K²α (n))) = o (n (nkα (n))) = o (n²Kα (N)) = O (N²α (n)) منذ K هو ثابت.

نظرا لأن α (n) لجميع الأغراض العملية هو أيضا ثابت، فإن الوقت الإجمالي يحدها O (N²).