对来自多个列表的元素进行分组

Question

我有以下数据结构：

基本上我有一个列表，其中包含其他列表（它们的大小可以是任意的，在我的例子中，所有 4 个列表的大小都是 2）。我必须进行分组，以便将具有相同元素的列表归为一个列表（也许不是最好的表述，但我无法更好地表述）。在我的例子中，结果应该如下： [72, 83, 127] 和 [110, 119].

例如，如果第三个子列表包含元素[83, 127, 55, 22]，则结果应如下所示：[72, 83, 127, 55, 22] 和[110, 119]。（所以我必须包括所有子列表元素）。

我怎样才能在 Java 或 Groovy 中做这样的事情？

Answer 1

由于您必须处理整个列表，一个不错的选择是利用 groovy 集合的 inject 方法（添加 println 以显示步骤）：

def values = [[72, 83], [72, 127], [83, 127], [110, 119]]

def result = values.inject([], { res, value -> 
    println "res = $res | value = $value"
    def found = res.find {
        if (it.intersect(value)) {
            it.addAll(value - it)
            true
        }
    }

    if (!found) {
        res << value
    }

    res
 })

 println result

 assert [[72, 83, 127], [110, 119]] == result

这样：

res = [] | value = [72, 83]
res = [[72, 83]] | value = [72, 127]
res = [[72, 83, 127]] | value = [83, 127]
res = [[72, 83, 127]] | value = [110, 119]
[[72, 83, 127], [110, 119]]

编辑：上述解决方案在某些情况下效果不佳，即

def values = [[72, 83], [72, 127], [83, 127], [110, 119], [47, 56], [56, 72]]

产量

[[72, 83, 127, 56], [110, 119], [47, 56]]

如果列表已排序，它会产生（我认为这是正确的解决方案）

[[47, 56, 72, 83, 127], [110, 119]]

编辑（2）： 解决上一个问题的更好的解决方案（即，一个列表共享元素与多个结果列表）：

def values = [[72, 83], [72, 127], [83, 127], [110, 119], [120, 121], [121, 127]]

def result = values.inject([], { res, value -> 
    println "res = $res | value = $value"
    def found = res.findAll { it.intersect(value) }
    println "  -> found = $found"

    if (!found) {
        res << value
    } else {
        res.removeAll(found)
        def merged = found.collect({ it + value as Set }).flatten() as Set
        println "  -> merged = $merged"
        res << merged
    }

    println "  => res = $res"
    res
})

Answer 2

这里是 java 使用地图的实现。首先，我们将 ArrayList 转换为映射，即 key=integerInList + value=NoOfOccurrence。然后我们只搜索地图中的每个元素，如果元素出现超过 1 次，那么我们只需添加到相应的组 (Set)。

public static void find() {
    //Input Data
    ArrayList<List<Integer>> list1 = new ArrayList<>();
    list1.add(Arrays.<Integer>asList(72, 83));
    list1.add(Arrays.<Integer>asList(72, 127));
    list1.add(Arrays.<Integer>asList(83, 127));
    list1.add(Arrays.<Integer>asList(110, 119));

    Map<Integer, Integer> map = new HashMap<>();

    //Convert Input Data to Map
    for (List<Integer> integers : list1) {
        for (Integer integer : integers) {
            int integer1=1;
            if (map.containsKey(integer)) {
                integer1 += map.get(integer);
            }
            map.put(integer, integer1);
        }
    }

    Set<Integer> group1 = new HashSet<>();
    Set<Integer> group2 = new HashSet<>();
    //find and build groups
    for (List<Integer> integers : list1) {
        boolean found = false;
        for (Integer integer : integers) {
            if (map.containsKey(integer)) {
                if (map.get(integer) > 1) {
                    found = true;
                    break;
                }
            }
        }
        if (found) {
            group1.addAll(integers);
        } else {
            group2.addAll(integers);
        }
    }

    System.out.println("group1 = " + group1);
    System.out.println("group2 = " + group2);
}

对来自多个列表的元素进行分组

Group elements from multiple lists

java

groovy

list