合并子阵列

Question

假设我们有一个阵列：

def a = [[0], [1], [2], [2, 1], [1, 2], [3, 2], [2, 3], [3], 
     [4, 3], [3, 4], [4], [5], [6], [8], [10, 7], [7, 10], 
     [7, 8], [8, 7], [9], [10], [7, 10, 8], [8, 9], [9, 8], 
     [11, 0], [0, 11]] 

然后

def b = reduce(a)

应产生

[ [0, 11], [1, 2, 3, 4], [5], [6], [7,8,9,10] ] 

我的逻辑是有一个包含结果的新数组reducedObjects。将objects的第一个子数组复制到reducedObjects，然后检查下一个子数组是否与来自reducedObjects的子数组具有交集。如果有交集，则从reducedObjects的子数组和原始子数组中创建一个联合。

def reduce(objects) { 
    def reducedObjects = new ArrayList() 
    objects.each { object -> 
     if (reducedObjects.size() == 0) { 
      reducedObjects << object 
     } else { 
      def isReduced = false 
      for (int i = 0; i < reducedObjects.size(); i++) { 

       def equals = false 
       object.each { it -> 
        if(reducedObjects[i].contains(it)) { 
         equals = true 
         isReduced = true 
        } 
       } 
       if (equals) { 
        reducedObjects[i] = (object + reducedObjects[i]).unique().sort() 
        reducedObjects.unique() 
       } 

      } 
      if(!isReduced) { 
       reducedObjects << object 
      } 
     } 
    } 
    return reducedObjects.unique() 
} 

以下功能不正常工作，因为结果是：

[[0, 11], [1, 2, 3, 4], [5], [6], [7, 8, 9, 10], [8, 9]] 

的问题是，reducedObjects有一个子阵[7, 8]再下一子阵列[9]。该函数将创建一个新的子阵列，因为没有交集，但是在下一次迭代中，有一个子阵列[8,9]，它合并在[7,8]和[9]中。

有没有更好的解决方案来做到这一点？或者以某种方式改进这个解决方案？

Answer 1

要在我的评论扩大上面 - 我认为问题就出在这里：

for (int i = 0; i < reducedObjects.size(); i++) { 

    def equals = false 
    object.each { it -> 
     if(reducedObjects[i].contains(it)) { 
      equals = true 
      isReduced = true 
     } 
    } 
    if (equals) { 
     reducedObjects[i] = (object + reducedObjects[i]).unique().sort() 
     reducedObjects.unique() 
    } 

} 

在这里，你迭代的输入列表（从该列表是object当前项目）和对象比较所有先前缩小的列表并合并它们，但对于每个缩小的列表，它将被合并。

想象一下你reducedObjects看起来像[[7,8],[9,10]]和对象是[8,9] - 那么这段代码将合并object[8,9]与这两个现有项目。

更地道的常规做法可能是这样的：

def a = [[0], [1], [2], [2, 1], [1, 2], [3, 2], [2, 3], [3], 
    [4, 3], [3, 4], [4], [5], [6], [8], [10, 7], [7, 10], 
    [7, 8], [8, 7], [9], [10], [7, 10, 8], [8, 9], [9, 8], 
    [11, 0], [0, 11]] 

def reduced = [] 

a.each{ incoming -> 
    List allReducedLists = (reduced.findAll{ r -> incoming.intersect(r) } + incoming).flatten().unique() 
    reduced = reduced.findAll{ r -> !allReducedLists.intersect(r) } 
    reduced << allReducedLists 
} 

println reduced 

（未测试超出上述输入，所以也许错过了某些情况下）

Answer 2

这里是你有一个使用递归的另一种选择关闭：

def a = [[0], [1], [2], [2, 1], [1, 2], [3, 2], [2, 3], [3], 
    [4, 3], [3, 4], [4], [5], [6], [8], [10, 7], [7, 10], 
    [7, 8], [8, 7], [9], [10], [7, 10, 8], [8, 9], [9, 8], 
    [11, 0], [0, 11] 
] 

def reducedList 
reducedList = {l-> 
    def r = [] 
    def found = false 
    l.each{a1-> 
     found = false 
     l.each{a2-> 
      if(a1!=a2){ 
       if(a1.intersect(a2).size()>0){ 
        r.push(a1.plus(a2).sort().unique()) 
        found = true 
       } 
      } 
     } 
     if(found==false)r.push(a1.sort().unique()) 
    } 
    return (r.unique()==l)?r.unique():reducedList(r) 
} 
println reducedList(a) //[[0, 11], [1, 2, 3, 4], [5], [6], [7, 8, 9, 10]]