创建组从集结点

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

我假设我可以得到的数据在作为一个array/object结构和操纵，然后吐得到的结构在任何格式的需要。

这将是一个再加上如果：

• 所有团体有至少2节点和2套。
• 当一个子集中的节点被包含在一个更大的设置，形成一个群组，然后只有在更大的组取得的一个组：在这个例子中，节点1,2没有一组自己的，因为所有的套他们的共同点已经出现在第2组.

(套被储存在XML，我们也设法把叉迄今为止，但这是无关紧要的。我可以理解的程序(伪)代码，但也喜欢的东西的骨架在XSLT或者拉斯卡拉可能的帮助，以获得启动的，我猜测。)

Answer 1

1. 通过列表的集。对于每个组S
   1. 通过列表的群体。对于每个组G的
      1. 如果可以是一个成员的G(即如果克的设置是一个子集S)下，增加S G
      2. 如果不能将一个成员的G但是，交叉S ang克的设置包含多个节点，使一个新的小组，交叉点，并将它添加到名单。
   2. 给一个集团的其自己的和将它添加到名单。
   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);
        }
        }

}