识别集合集合中的数字集合

Question

我有一个集合，里面有数字。说

A = {-2, 5, 6, 8}  
B = {-2, 4}  
C = {-2, 4, 6, 8}  
D = {1, -2, 15}  
E = {1, 4, 15}  
F = {1, 15}  
G = {2, 5, 6, 15}  
H = {2, 6, 15}  

现在我想找一个有4个数字的集合，然后找出属于这个集合的集合。例如，我可以在这里定义一个集合X = {1, -2, 4, 15}，可以看到B，D，E和F属于这个集合。找到这些集合并不是很困难。

然而，我面临的问题是，我想标识这个集合中所有长度为m个数字的集合。因此，实际上，当将上面的示例作为输入时，一个算法将m = 4和{A,B,C,D,E,F,G,H}作为输入，并给出{B,D,E,F}和{B, C} (因为它们都包含集合{-2，-4，6，8}中的数字)。

我能想出答案的唯一方法是用可用的集合中的数字生成所有可能的length = 4集合，并确定是否每个集合都适合。这看起来有点生硬。

有什么好建议吗？(Java或PHP)？

Answer 1

我会递归地解决这个问题。考虑一组。如果从这个集合中提取元素会带来大于m的元素数量，那么考虑下一个集合。从这个集合中获取元素。如果没有更多的集合需要考虑，那么您将有一些集合作为可能的结果。如果此结果中的元素数等于m，则采用此结果。现在“不考虑”上一个考虑的集合，然后考虑下一个集合。重复以上步骤，直到不再有需要考虑的集合。最后，删除作为现有结果子集的所有结果。

Answer 2

在Java语言中，您可以使用集合的retainAll()方法或静态方法Collections.disjoint(a,b)来查找这两个集合中包含的元素，或者只检查它们是否具有公共元素。

示例：

Set<Integer> setA = new HashSet<Integer>();
setA.add( -2 );
setA.add( 5 );
setA.add( 6 );
setA.add( 8 );

Set<Integer> setB = new HashSet<Integer>();
setB.add( -2 );
setB.add( -4 );
setB.add( 6 );
setB.add( 8 );

//fill with all values from setA
HashSet<Integer> setAB = new HashSet<Integer>( setA );
//keep only those values that are contained in setB as well
setAB.retainAll( setB );


System.out.println( setAB ); //prints "[-2, 8, 6]"

System.out.println( "A and B overlap: " + !Collections.disjoint( setA, setB ) ); //prints "A and B overlap: true"

如果你有一个集合集合，比如List<Set<Integer>>，对它们进行迭代，并将每个集合与输入集合进行比较。

或者，您可以使用Apache Commons Collections类CollectionUtils，它提供了像CollectionUtils.containsAny( collection1,collection2 )或CollectionUtils.union( collection1,collection2 )这样方便的方法。

Google Guava可能也有一个类似的类。