一個發現設置組陣列

的共同要素的假設有幾個數組：一個發現設置組陣列

A. [1,2,3,4,5,6,7,8,9,10] 
B. [2,4,6,8,10] 
C. [1,4,7,10] 
D. [1,3,5,7,9] 
. 
.

我需要找出元素的所有可能集（1,2,3,4,5 ...）各

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

實際輸入是包含字符串的文件：其中在-至少2門陣列（A，B，C ....），並將其顯示在下面的方式是常見的。可能有數千個文件，每個文件可能包含超過一百個密鑰字符串。

我試過以下方法：首先我通過比較所有可能的數組對來生成元素集。然後我嘗試使用邏輯來生成其他集合 - 元素集合的交集在數組集合中很常見。就像這樣：

(2,4,6,8,10) -> (A,B) 
(1,4,7,10) -> (A,C)

從上面我們可以得到：

intersect((2,4,6,8,10),(1,4,7,10)) -> union((A,B),(A,C)) 
or, (4,10) -> (A,B,C)

是否有其他辦法，我可以嘗試提高時間和內存的複雜性 - 考慮包含數百個各元素的千元輸入文件？

來源

2014-07-09 user3819093

我會用下面的方法。

掃描整個數據以獲取數據中出現的一組元素。
維護每個元素的計數器;如果它發生，再次掃描數據並增加每個元素的計數器。
丟棄出現少於2次的所有元素。
生成剩餘元素的所有可能子集。對於每個子集，如果發生該集合的任何元素，則掃描數據並輸出每個數組標識符。

來源

2014-07-09 07:34:49 Codor

使用哈希映射（或映射，如果您需要擔心碰撞）。下面的僞代碼：

for file in file_list: 
    for word in file: 
     hash_map[word].append(file) 

for wordkey in hash_map: 
    print pick_uniques(hash_map[wordkey])

這種方法的複雜度爲O（字數總數），忽略每個單詞的長度。

編輯：既然你也想合併wordkey s與pick_uniques(hash_map[wordkey])相同，你可以應用相同的哈希映射方法，這次是反轉鍵。

來源

2014-07-09 08:00:04 Pradhan

該Java類：

public class Store { 
Map<Integer,Set<String>> int2keyset = new HashMap<>(); 
Set<Set<String>> setOfKeyset = new HashSet<>(); 

public void enter(String key, Integer[] integers){ 
    for(Integer val: integers){ 
     Set<String> keySet = int2keyset.get(val); 
     Set<String> newKeySet = null; 
     if(keySet == null){ 
      newKeySet = new HashSet<String>(); 
      newKeySet.add(key);  
     } else { 
      newKeySet = new HashSet<>(keySet); 
      newKeySet.add(key); 
     } 
     setOfKeyset.remove(newKeySet); 
     setOfKeyset.add(newKeySet); 
     int2keyset.put(val, newKeySet); 
    } 
} 

public void dump(){ 
    Map<Set<String>,Set<Integer>> keySet2intSet = new HashMap<>(); 
    for(Map.Entry<Integer,Set<String>> entry: int2keyset.entrySet()){ 
     Integer intval = entry.getKey(); 
     Set<String> keySet = entry.getValue(); 
     Set<Integer> intSet = keySet2intSet.get(keySet); 
     if(intSet == null){ 
      intSet = new HashSet<Integer>(); 
     } 
     intSet.add(intval); 
     keySet2intSet.put(keySet,intSet); 
    } 
    for(Map.Entry<Set<String>,Set<Integer>> entry: keySet2intSet.entrySet()){ 
     System.out.println(entry.getValue() + " => " + entry.getKey()); 
} 
} 
}

當與問題中給出的線路饋送生產：

[2, 6, 8] => [A, B] 
[3, 5, 9] => [A, D] 
[4, 10] => [A, B, C] 
[1, 7] => [A, C, D]

儘管它不是相同的預期的輸出，它包含所有的信息，以產生，並且更加緊湊。如果預計會有大量的輸入行，那麼可能需要採取一種方法來保持所存儲的信息儘可能緊湊，並且我試圖遵循這一準則。

來源

2014-07-09 18:02:30 laune

一個發現設置組陣列

回答

相關問題