一个发现设置组阵列

的共同要素的假设有几个数组：一个发现设置组阵列

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

一个发现设置组阵列

回答

相关问题