Создание групп из наборов узлов
-
10-07-2019 - |
Вопрос
У меня есть список наборов (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 не имеют собственной группы, поскольку все наборы, которые у них общие, уже присутствуют в группе2.
(Наборы хранятся в формате XML, который мне пока также удалось преобразовать в JSON, но это не имеет значения.Я могу понять процедурный (псевдо)код, но я думаю, что что-то вроде скелета в XSLT или Scala могло бы помочь начать работу.)
Решение
- Пройдитесь по списку наборов.Для каждого набора S
- Пройдитесь по списку групп.Для каждой группы G
- Если S может быть членом G (т.е.если множество G является подмножеством S), добавьте S к G.
- Если S не может быть членом G, но пересечение множества S и G содержит более одного узла, создайте новую группу для этого пересечения и добавьте ее в список.
- Создайте S собственную группу и добавьте ее в список.
- Объедините любые группы, имеющие одинаковый набор.
- Пройдитесь по списку групп.Для каждой группы G
- Удалите любую группу, состоящую только из одного набора участников.
Например, с вашими наборами примеров после прочтения a и b список групп будет
[1,2,5,6] [a] [1,5] [a,b] [1,4,5] [b]
И после прочтения c это
[1,2,5,6] [a] [1,5] [a,b,c] [1,4,5] [b] [1,2,5] [a,c]
Если скорость является проблемой, существуют немного более эффективные алгоритмы.
Другие советы
/*
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);
}
}
}