拼合具有自引用列表的列表

我有名單列表，其中包括對自身的引用，我需要扁平化這個列表。例如：
例如。我有列表

A = [1，[2，[3]]，A，]

扁平列表是這樣的

A = [1,2 ，3]

這是我（在Java中）曾嘗試：

public static void flattenRecurser(List<Integer> result, List<?> nested) {   
    for (Object item : nested) { 
     if (item instanceof List<?> && !freq.containsKey((List<?>) item)) { 
      flattenRecurser(result, (List<?>) item); 
     } else if (item instanceof Integer) { 
      result.add((Integer) item); 
     } 
    } 
}

我打電話flattenRecurser

static Map<List<?>, List<?>> freq = new HashMap<>(); 

freq.put(nested,nested); 
List<Integer> result = new ArrayList<Integer>(); 
flattenRecurser(result, nested);

前添加嵌套映射稱爲頻率，但我得到一個錯誤，當我把在頻率地圖嵌套列表。
查找嵌套對象的哈希碼導致錯誤。我將如何以不同的方式來解決這個問題，或者有辦法找到嵌套對象的散列。
這裏是我的錯誤：在線程

異常「主」 java.lang.StackOverflowError的處 java.util中 java.util.ArrayList.iterator（ArrayList.java:834）。 AbstractList.hashCode（AbstractList.java:540）

我沒有行號834或540在我的代碼在所有

來源

2016-02-27 sreeprasad

你能發佈錯誤嗎？還有你的嵌套對象聲明？ – SomeDude

你爲什麼要添加嵌套到地圖？只是比較參考列表A本身，如果它是相同然後繼續前進。 – piyush121

我不能真正包裹我的頭，看看'A = [1，[2，[3]]，A]'的扁平列表應該如何顯示。只是'[1,2,3]'或者[1,2,3,1,2,3]'，或者如何？你能提供一些例子嗎？ –

您必須跟蹤已經添加到結果列表中的列表。你可以用一個哈希集合做到這一點，但似乎是一個bug與List.hashCode實現（？）：雖然List.toString可以處理包含自引用，List.hashCode運行列表進入一個無限遞歸。相反，您可以使用System.identityHashCode。

public static List flatten(List flatten, Set<Integer> ignore) { 
    List result = new LinkedList(); 
    ignore.add(System.identityHashCode(flatten)); 
    for (Object o : flatten) { 
     if (o instanceof List) { 
      if (! ignore.contains(System.identityHashCode(o))) { 
       result.addAll(flatten((List) o, ignore)); 
      } 
     } else { 
      result.add(o); 
     } 
    } 
    return result; 
}

實施例：

List C = new ArrayList(Arrays.asList(4, 5, 6)); 
List B = new ArrayList(Arrays.asList(2, 3, C, 7)); 
List A = new ArrayList(Arrays.asList(1, B, 8, 9, C)); 
C.add(C); 
B.add(B); 
A.add(A); 

System.out.println(A); 
System.out.println(flatten(A, new HashSet<>()));

輸出：

[1, [2, 3, [4, 5, 6, (this Collection)], 7, (this Collection)], 8, 9, [4, 5, 6, (this Collection)], (this Collection)] 
[1, 2, 3, 4, 5, 6, 7, 8, 9]

注意這裏可以是這種方法的衝突，具有相同身份哈希碼即兩個不同列表。在這種情況下，其中一個列表不會被添加到結果中。另外，您也可以循環整個ignore集，每個元素與==比較當前列表。

來源

2016-02-27 20:50:21

很好的答案。將看看system.identityHashcode是如何工作的。是的，我認爲這不僅僅是一個問題，而且是任何具有自我引用的數據結構的問題。 – sreeprasad

剛纔注意到'List.toString'在兩個列表「纏結」時出現類似的問題，即'a = [b]'和'b = [a]'，產生了一個StackOverflow錯誤。 Python可以處理這個（只會打印'[[[...]]]'） –

你具有無限遞歸。如果item ==嵌套 - >什麼也不做。

來源

2016-02-27 20:24:41

拼合具有自引用列表的列表

回答

相關問題