Java算法：如何对实体进行分组

Question

有实体列表：A、B、C、D。 每个实体都有自己的其他实体列表，LAT表示：

• A（1,2,3）
• B（4、5、6）
• C（1，2）
• D（8、9）

我需要通过第二级实体元素的交集对第一级实体进行分组。最后，我应该得到如下结果：

List<Set<Entity1>>: 

 - A(1, 2, 3), C(1, 2)
 - B(4, 5, 6)
 - D(8, 9)

如何在java7中编写它

Answer 1

一种选择是使用某种列表，并对它们进行比较。 另一种选择是使用实矩阵，假设行是实体，列是数字。如果实体和数字的组合为真，则使用X或1。然后遍历获得匹配项的列（所有列都有多个元素）

为了简单起见，请参见清单（虽然性能不高，但可以完成这项工作）：

    HashMap<String, List<String>> entities = new HashMap<String, List<String>>();
    List<String> a = new ArrayList();
    a.add("1");
    a.add("2");
    a.add("3");
    List<String> b = new ArrayList<>();
    b.add("4");
    b.add("5");
    b.add("6");
    List<String> c = new ArrayList<>();
    c.add("1");
    c.add("2");
    List<String> d = new ArrayList<>();
    d.add("8");
    d.add("9");

    entities.put("A",a);
    entities.put("B",b);
    entities.put("C",c);
    entities.put("D",d);
    System.out.println("Check");
    entities.forEach( (entity, list) -> {
        entities.forEach( (otherEntity, otherList) -> {
            if (! entity.equals(otherEntity)) {
                // System.out.println(entity + otherEntity + list + " versus " + otherList);
                list.forEach(l -> {
                    otherList.forEach(o -> {
                        // System.out.println(" " + l + o);
                        if (l.equals(o))
                            System.out.println("hit:" + entity + " and " + otherEntity);
                    });

                });
            }
        });
    });

Answer 2

不是一个真正的答案，但太简短，无法评论

我不确定是否有需求，但这可能吗

• A（1,2）
• B（2,3）
• C（3,4）

结果将是

• A、 B，C

不是最优算法（伪代码）

1: initially each entity is a group
2: for each pair of group identify if there is intersection
3:     if there is, merge the groups
4:     if there is not you are done = you have groups
5: repeat the for loop while the group number is decreasing

这不是最优的，但可能是一个良好的开端

以上示例的详细描述

1. 你有组[ {A}(1, 2), {B}(2, 3), {C}(3, 4) ]
2. 你确定A和B有共同的“关系”——2
3. 合并后，新的组将被[ {A, B}(1, 2, 3), {C}(3, 4) ]
4. 你继续发现，第一组和第二组有共同的关系-3
5. 合并后，新的组将被[ {A, B, C}(1, 2, 3, 4) ]

为了简化您的实现，您可以为group创建一个相关实体的列表

---

例如，对于新输入-[ {A}(1, 2), {B}(3, 4), {C}(1 ,3) ]，我在伪代码中添加了行号

• 我们最初有三个小组
• 伪代码中的第2行基本上是循环的第2行，假设你识别A和C相交
• 在第3行中，您合并到[ {A, C}(1, 2, 3), {B}(3, 4) ]
• pseudo中的第5行将您返回到第2行，最初您有3个组，您合并了，组的数量减少到了2个
• 继续识别交叉点并合并到一个组