العضوية خوارزمية المشتركة

Question

ويمكن للناس أن تنتمي إلى واحدة أو مجموعات عديدة. ما هو خوارزمية جيدة لعضوية مشتركة الإخراج؟

وأي الأشخاص A و B في المجموعات C، D، E و ... الخ

لغتي المفضلة ستكون روبي (أو <م> ربما بيثون)، ولكن أي رمز أو شبة الكود موضع تقدير كبير.

Answer 1

وانها خوارزمية بسيطة جدا، في الواقع (على الأقل بالنسبة لأعداد معقولة من المستخدمين والمجموعات).

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

وهكذا، إذا كان الشخص في المجموعة K، M، N و، والشخص B وفي K، N، P و، عملتم على المجموعات التالية:

A := {K, M, N}
B := {K, N, P}
intersect(A, B) = {K, N}

في روبي، يمكنك استخدام معيار Set الطبقة مكتبة لأداء هذه الحسابات:

require 'set'
memberships_a = Set[:K, :M, :N]
memberships_b = Set[:K, :N, :P]
shared = memberships_a.intersection(memberships_b)
# you can also use the '&' operator as shorthand for 'intersection'
shared_2 = memberships_a & memberships_b

Answer 2

هل تقصد شيئا مثل أدناه؟ (الثعبان):

>>> a_groups = set(["A", "B", "C"])
>>> b_groups = set(["B", "C", "D"])
>>> print a_groups & b_groups
set(['C', 'B'])
>>>

Answer 3

هل تحاول العثور على أي شيء على وجه الخصوص حول عضوية؟ أم أنك مجرد محاولة للعثور على جميع عضويات ... أي:

A - No group
B - Groups 1, 2, 3
C - Groups 2, 5
D - Groups 2, 3, 4

إذا كان هذا الأخير، وأنا لا أعتقد أن هناك خوارزمية خاصة للقيام بذلك. طالما التحقق من أن يكون الشخص في مجموعة يأخذ O (1) أفضل رهان هو O (M * N) القوة الغاشمة الخوارزمية.

For each person O(N) {
   Create a set for this person
   For each group O(M) {
       if the person is in the group, add this group to the set O(1) when using maps/hashed structures
   }
   output the set
}

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