什么是从一组集合中找到所有不相交集合的算法？

我有'n'套（n < 10）。每组可能有1000个元素。我想找到这些集合的所有不相交集合。说，例如，我有套什么是从一组集合中找到所有不相交集合的算法？

A = {2,5,6,7}, B = {5,1} and C = {5,7}.

然后输出将是{{5}, {2,6}, {1}, {7}}。什么可以是这个算法？我想过找到两两不相交的集合，然后使用这些新的（不相交的）集合再次找到剩下的集合中的不相交集合。但是这不会很好地扩展。希望这有助于：Diagram Example

来源

2016-01-09 aceBox

你可以说一下关于输出的属性，或者更好地获得它的内容吗？例如，为什么不包括{2}和{6}？ – davidhigh

@davidhigh考虑它是这样的：你有2个集合A和B.不相交集合是A-B，交集B和B-A。希望这有助于：https://doc-0c-a4-docs.googleusercontent.com/docs/securesc/i4h2cehd386i3qiqgfp2t1a9r0fu5o6m/qhu2v38hp0h1pdvvehj9vgmdsctujsbt/1452340800000/02075453514295040169/02075453514295040169/0BzbXcZ2xK6JrZ1NiblVXeGpMYms?h=07006165945320890235&nonce=89dl1pkjorq58&user=02075453514295040169&hash=7is7r402mkd2ag6amo4l23vn1bp5cqfd – aceBox

无法连接到您的链接：/。解决方案可以将您的问题视为双入口映射：行将是元素和列集。我会尽力写一份草稿。 – 88877

你可以把你的问题看作是一个布尔两条入口映射，元素是行，集合是列，布尔是问题的答案是包含在集合中的元素。比如你的例子是：

然后创建用于描述型动物的每个元素的关键将是在和一个地图注册此元素。

举例来说，如果我们考虑的主要创作功能是这样的：

int keyFunction(bool Xa, bool Xb, bool Xc) { 
    int key =0; 
    if (Xa) {key+=4;} 
    if (Xb) {key+=2;} 
    if (Xc) {key+=1;} 
    return key; 
}

然后，我们可以创建地图：

Key ElementsQueue 
0 [] 
1 [] 
2 [1] 
3 [] 
4 [2,6] 
5 [7] 
6 [] 
7 [5]

，并返回该地图的元素。

来源

2016-01-09 13:14:20 88877

如果这个解决方案对你来说看起来不错，我会试着写一个实施草案 – 88877

你是如何将关键值设定为4,2,1的？ – aceBox

@aceBox我们可以将布尔列表视为二进制数的位。所以[x，y，z]是x * 2^2 + y * 2^1 + z * 2^0。 – 88877

什么是从一组集合中找到所有不相交集合的算法？

回答

相关问题