مجموعة من المجموعات التي لا تحتوي على مجموعات والتي تعتبر مجموعة فرعية من مجموعة أخرى في المجموعة

Question

أنا أبحث عن بنية بيانات مجردة تمثل مجموعة من المجموعات بحيث لا تكون أي مجموعة في المجموعة مجموعة فرعية من مجموعة أخرى في المجموعة.

وهذا يعني أنه عند الإدراج سيتم استيفاء الشروط التالية:

أ.سيؤدي إدراج عنصر يمثل بالفعل مجموعة فرعية من عنصر آخر إلى إرجاع المجموعة الأصلية.

ب.سيؤدي إدراج عنصر يمثل مجموعة شاملة لأي عناصر أخرى إلى إنشاء مجموعة مع إضافة المجموعة الشاملة وإزالة المجموعات الفرعية.

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

أتساءل عما إذا كانت هناك بنية بيانات تسمح بالوفاء بـ B بسرعة أيضًا.

Answer 1

سيكون النهج التافه هو الاحتفاظ بقائمة من المجموعات وإجراء بحث خطي من خلالها لكل مجموعة واردة (اختبار ما إذا كانت المجموعة الواردة عبارة عن مجموعة فرعية).

من الواضح أن هذا يعمل في وقت O(n) للبحث الخطي وربما حجم O(m) لحجم المجموعة الواردة.وبالتالي O(n*m) الوقت الإجمالي (عدد المجموعات مقابل.حجم كل مجموعة).

التحسين الأكثر وضوحًا، بالطبع، هو فهرسة الأحجام المحددة.ثم تقوم فقط باختبار كل مجموعة واردة مقابل تلك التي لها نفس الحجم أو أكبر.(المجموعة لا يمكن أن تكون مجموعة فرعية من أي مجموعة أصغر، دوه!).

التحسين التالي الذي يتبادر إلى الذهن هو إنشاء فهرس للعناصر.وبالتالي، بالنسبة لكل مجموعة واردة، ستجد تقاطع كل مجموعة تحتوي على كل عنصر من العناصر.بمعنى آخر، إذا وجدنا، بالنسبة للمجموعة الواردة {a,b,c}، أن العنصر {a} موجود في المجموعات A وB وD، فإن العنصر {b} موجود في B وE وF و{c} موجود في A و B و Z ...فإن المجموعة الواردة هي مجموعة فرعية من B (تقاطع {A، ​​B، D}، {B، E، F}، و{A، B، Z}).

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

Answer 2

فكرة تافهة، والتي ستعمل في O(K) حيث K هو حجم العنصر الذي تتم إضافته.

• احتفظ بالمجموعات بأي طريقة تريدها
• احتفظ بخريطة set_id -> set_size
• احتفظ بخريطة الكائن -> set_id

كلا A و B هما O(K).

Answer 3

وإذا كان أفراد مجموعتك A، B، ... يتم تعيين على أعداد أولية واضحة (ونسبيا)، وجنبا إلى جنب مع كل مجموعة تقوم بتخزين المنتج من جميع أعضاء كما ص (A)، ص (B) الخ ثم الفرعية وsupersets يمكن العثور عليه سواء ص (X) هو عامل ص (Y) أو العكس بالعكس.

هل يمكن أن ينتهي الأمر مع بعض أعداد كبيرة جدا أعتقد، ولكنه يعمل من الناحية النظرية.

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

وإذا [أ ب ج د] -> [2 3 5 7]، ص (اي بي سي) = 30، ص (عبد) = 42، ص (قبل الميلاد) = 15، ص (ABCD) = 210

Answer 4

ما موقع dorky! لقد سجلت الآن، لذلك قد تكون قادرة على التعليق على الاشياء من أمس في الوقت المناسب. حتى ذلك الحين، ولكن ...

وStephen C: على الرغم من أنني أعتقد أن لغتي الإنجليزية لتكون كافية ويبدو لي أن حصلوا على explicator: أنه غاب بت بها، ومع ذلك، وتعليقه على النحو التالي:

---

<اقتباس فقرة>   

وStephen C: العثور على العوامل ل   عدد التعسفي هو في الواقع NP كاملة، ولكن لا صلة هنا. ال   المسألة هي ما إذا كان أصغر من اثنين   أرقام بالضبط يقسم أكبر، ل   تشغيل معامل بسيطة. فمثلا،   ص (قبل الميلاد) = 15 هو المقسوم ص (ABCD) = 210،   حتى قبل الميلاد هو مجموعة فرعية من ABCD (وكذلك مجموعات عبد   واي بي سي).

     

وإضافة مجموعة جديدة سنغافوري للمجموعة موجودة من مجموعات N هو O (N)، على افتراض أن المقارنة وتقسيم الأعداد الكبيرة يأخذ نفس الوقت تقريبا بغض النظر عن N.

     

للكل إدخال E الموجودة في مجموعة من مجموعات، وتوقف إذا ص (S)   

ص (E) وص (E) الانقسامات ص (S) بالضبط. إضافة S إذا كنت تحصل على نهاية المجموعة. مجموعة   من BigNums ستعمل.

---

وJL: إذا كنت ترغب في أن يكون لي في الموقع مطارد يرجى تسعى إلى 1) إضافة قيمة 2) بدقة