الاتحاد / تقاطع 2 مجموعات، حيث يتم تعريف كل مجموعة من مجموعات فرعية انها

Question

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

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

وA = B اتحاد {1،2}

وB = C اتحاد D

C = {5،6}

وD = {5،7}

E = {4}

وبعد ذلك A = {1،2،5،6،7}

ونقابة E = {1،2،4،5،6،7}

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

Answer 1

وهكذا كان لديك تسلسل هرمي ثابت النقابات تغيير مجموعات؟ وكنت، كما في المثال الخاص بك، مهتمة فقط في قيمة مجموعة واحدة؟

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

لالاستغناء عن النقابات جار إعادة حساب كلما مجموعة أوراق التغييرات، هل يمكن أن تتبع لكل عنصر في كم مجموعات ويرد عليه حاليا. يمكن تحديث هذا بسرعة إذا ورقة تبدأ التغيرات، وتلك التي لا تبحث المطلوبة في أي مجموعات ورقة دون تغيير. ثم، تلك العناصر مع تردد عد> 0 حاليا في الاتحاد.

Answer 2

وربما كنت تبحث عن نوع من مجموعة منفصلة هيكل البيانات؟

Answer 3

والعديد من الأسئلة حول هذه القضية.

والسؤال الأول: إلى متى يعني هذا "السيناريو" / "برنامج" لديك لتشغيل؟ في حال انها ليست طويلة جدا، فإنه يمكن أن يكون جيدا خيارا جيدا لمجرد تخزين الاتحادات السابقة ومخبأ فحص قبل تنفيذ العمل النقابي. الذاكرة ليست مكلفة في الوقت الحاضر:)

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