إنشاء مجموعات من مجموعات من العقد

Question

لدي قائمة بالمجموعات (a،b،c،d،e في المثال أدناه).تحتوي كل مجموعة على قائمة العقد في تلك المجموعة (1-6 أدناه).كنت أتساءل أنه من المحتمل أن تكون هناك خوارزمية عامة معروفة لتحقيق ما يلي، وأنا لا أعرف عنها.

sets[
 a[1,2,5,6],
 b[1,4,5],
 c[1,2,5],
 d[2,5],
 e[1,6],
]

أرغب في إنشاء هيكل جديد، قائمة بالمجموعات، مع وجود كل مجموعة

• جميع المجموعات (الفرعية) من العقد التي تظهر في مجموعات متعددة
• مراجع للمجموعات الأصلية التي تنتمي إليها تلك العقد

وبالتالي تصبح البيانات المذكورة أعلاه (ترتيب المجموعات غير ذي صلة).

group1{nodes[2,5],sets[a,c,e]}
group2{nodes[1,2,5],sets[a,c]}
group3{nodes[1,6],sets[a,e]}
group4{nodes[1,5],sets[a,b,c]}

أفترض أنه يمكنني الحصول على البيانات كبنية مصفوفة/كائن ومعالجتها، ثم إخراج البنية الناتجة بأي تنسيق مطلوب.

سيكون زائدا إذا:

• تحتوي جميع المجموعات على عقدتين ومجموعتين على الأقل.
• عندما تكون مجموعة فرعية من العقد موجودة في مجموعة أكبر تشكل مجموعة، فإن المجموعة الأكبر فقط هي التي تحصل على المجموعة:في هذا المثال، لا تحتوي العقد 1،2 على مجموعة خاصة بها نظرًا لأن جميع المجموعات المشتركة بينها تظهر بالفعل في المجموعة 2.

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

Answer 1

1. انتقل من خلال قائمة المجموعات.لكل مجموعة س
   1. انتقل من خلال قائمة المجموعات.لكل مجموعة G
      1. إذا كان من الممكن أن يكون S عضوًا في G (أي.إذا كانت مجموعة G هي مجموعة فرعية من S)، أضف S إلى G.
      2. إذا كان S لا يمكن أن يكون عضوًا في G ولكن تقاطع مجموعة S ang G يحتوي على أكثر من عقدة واحدة، فقم بإنشاء مجموعة جديدة لهذا التقاطع وأضفها إلى القائمة.
   2. أعط S مجموعة خاصة به وأضفها إلى القائمة.
   3. قم بدمج أي مجموعات لها نفس المجموعة.
2. احذف أي مجموعة تحتوي على مجموعة أعضاء واحدة فقط.

على سبيل المثال، مع مجموعات الأمثلة الخاصة بك، بعد قراءة a وb، تظهر قائمة المجموعات

[1,2,5,6] [a]
[1,5] [a,b]
[1,4,5] [b]

وبعد قراءة ج فهو

[1,2,5,6] [a]
[1,5] [a,b,c]
[1,4,5] [b]
[1,2,5] [a,c]

هناك خوارزميات أكثر كفاءة قليلاً، إذا كانت السرعة مشكلة.

Answer 2

/*
Pseudocode algorithm for creating groups data from a set dataset, further explained in the project documentation. This is based on 
http://stackoverflow.com/questions/1644387/create-groups-from-sets-of-nodes

I am assuming 
- Group is a structure (class) the objects of which contain two lists: a list of sets and a list of nodes (group.nodes). Its constructor accepts a list of nodes and a reference to a Set object
- Set is a list structure (class), the objects (set)  of which contain the nodes of the list in set.nodes
- groups and sets are both list structures that can contain arbitrary objects which can be iterated with foreach(). 
- you can get the objects two lists have in common as a new list with intersection()
- you can count the number of objects in a list with length()
*/

//Create groups, going through the original sets
foreach(sets as set){
    if(groups.nodes.length==0){
        groups.addGroup(new Group(set.nodes, set));
    }
    else{
        foreach (groups as group){
                if(group.nodes.length() == intersection(group.nodes,set.nodes).length()){
                    // the group is a subset of the set, so just add the set as a member the group
                    group.addset(set);
                    if (group.nodes.length() < set.nodes.length()){
                    // if the set has more nodes than the group that already exists, 
                    // create a new group for the nodes of the set, with set as a member of that group
                    groups.addGroup(new Group(set.nodes, set));
                    }
                }

                // If group is not a subset of set, and the intersection of the nodes of the group 
                // and the nodes of the set
                // is greater than one (they have more than one person in common), create a new group with 
                // those nodes they have in common, with set as a member of that group
                else if(group.nodes.length() > intersection(group.nodes,set.nodes).length() 
                    && intersection(group.nodes,set.nodes).length()>1){
                    groups.addGroup(new Group(intersection(group.nodes,set.nodes), set);
                }
        }
    }

}

// Cleanup time!
foreach(groups as group){
    //delete any group with only one member set (for it is not really a group then)
    if (group.sets.length<2){
        groups.remove(group);
    }
    // combine any groups that have the same set of nodes. Is this really needed? 
    foreach(groups2 as group2){
        //if the size of the intersection of the groups is the same size as either of the 
        //groups, then the groups have the same nodes.
        if (intersection(group.nodes,group2.nodes).length == group.nodes.length){
            foreach(group2.sets as set2){
                if(!group.hasset(set)){
                    group.addset(set2);
                }
            }
            groups.remove(group2);
        }
        }

}