Создать группы из наборов узлов

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]}

Я предполагаю, что могу получить данные в виде структуры массива / объекта и манипулировать ими, а затем выплюнуть полученную структуру в любом необходимом формате.

Было бы плюсом, если:

• все группы имели минимум 2 узла и 2 комплекта.
• когда подмножество узлов содержится в большем наборе, которое образует группу, тогда только больший набор получает группу: в этом примере узлы 1,2 не имеют собственной группы, поскольку все наборы, которые они имеют общие уже появляются в group2.

(Наборы хранятся в XML, который мне также удалось преобразовать в JSON, но это не имеет значения. Я могу понять процедурный (псевдо) код, но также что-то вроде скелета в XSLT или Scala может помочь получить началось, наверное.)

Answer 1

1. Просмотрите список наборов. Для каждого набора S
   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 
/1233325/sozdat-gruppy-iz-naborov-uzlov

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);
        }
        }

}