查找数组集合中常见的元素集合

Question

假设有几个数组：

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...)中的每一个在至少两个阵列(A，B，C....)并以下列方式显示它们:

(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,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)

有没有其他方法可以尝试提高时间和内存的复杂性 - 考虑每个包含数百个元素的千个输入文件？

Answer 1

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

虽然它与预期的输出不同，但它确实包含产生该输出的所有信息，并且更加紧凑。如果预期有大量的输入行，则可能值得采用一种使存储的信息尽可能紧凑的方法，我已尝试遵循此准则。

Answer 2

使用哈希映射（如果需要担心冲突，也可以使用映射）。伪代码如下：

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（单词总数），忽略了每个单词的长度。

编辑：由于您还想将wordkeys与相同的pick_uniques（hash_map[wordkey]）组合，因此您可以应用相同的哈希映射方法，这次反转键。

Answer 3

我将使用以下方法。

< li >扫描整个数据以获得数据中出现的一组元素。 < li >为每个元素维护一个计数器；再次扫描数据，并增加每个元素的计数器(如果出现的话)。 < li >丢弃出现次数少于2次的所有元素。 < li >生成剩余元素的所有可能子集。对于每个子集，扫描数据并输出每个数组标识符(如果集合中有任何元素出现的话)。