合併子陣列

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