在集合列表中查找元素的唯一子集

Question

我试图在集合列表中找到集合的唯一确定子集，即集合 A 的子集 E，使得 A 是唯一包含 E 的集合（我不确定数学上如何称呼它） 。 例如，对于以下集合列表：

set A: {2,3,5}
set B: {2,3}
set C: {2,3,7}
set D: {3,7}
set E: {2,11,13}
set F: {2}

独特的子集是：

set A: {5}
set B: {}
set C: {2,7}
set D: {}
set E: {{11},{13},{11,13}}
set F: {}

结果显示了类似于给定集合包含 2 和 7 的关系，它必须是集合 C，否则如果我们只有元素 3，我们无法确定唯一的集合。请注意，元素不一定需要是数字，它们可以可以是任何物体。

Answer 1

不确定你在这里所做的事情的名称，但从数学上讲，我会通过比较powersets的差异来接近它，但由于你只对子集感兴趣，所以从powerset中丢弃完整的集合（powerset是所有可能的子集，包括空集和全集）。

问题是找到一个集合相对于其他集合的幂集的唯一子集。在Python中，这是通过在所有

n - 1

中重复检查表示其他集合之一的幂集的元组列表中表示[给定集合]的特定子集的元组来完成的（因此在您的示例中为5）动力组。

这是 Python 中的一个实现，从包含您的输入的文本文件中读取：

from itertools import chain, combinations as comb
import re

def ProcessSet(l):
    """Turn a line [read from text file] into a tuple of (label, values)."""
    label = l[l.find(':')-1]
    vals = re.compile('{(.+)}').findall(l.rstrip())[0].split(',')
    return label, vals

def GetSubsets(s):
    """
    Get all subsets of a given set (including the empty set).
    """
    return list(chain(*map(lambda x: comb(s, x), range(0, len(s)))))

def GetPowerset(s):
    """
    Get the powerset of a given set (all subsets incl. empty and full set).
    """
    return list(chain(*map(lambda x: comb(s, x), range(0, len(s)+1))))

# read the text lines into a list
with open("set_list.txt", "r") as f:
    sets = [ProcessSet(l) for l in f.readlines()]

all_subsets = [GetSubsets(s[1]) for s in sets]
powersets  = [GetPowerset(s[1]) for s in sets]

for i in range(0, len(sets)):
    # declare label (l) and subsets (ss) for current loop iteration
    l, ss = sets[i][0], all_subsets[i]
    # list the other powersets to compare against
    ops = [x for ind, x in enumerate(powersets) if ind != i]
    # find unique subsets: those that are only a subset of the current set
    # and not found in the powerset of any of the other sets
    uss = list(set(ss)-set([x for y in ops for x in y if x in ss]))
    #uss = []
    #for s in ss:
    #    contains_s = [(s in ps) for ps in ops]
    #    if not any(contains_s):
    #        uss.append(s)
    str_uss = ', '.join([f"({', '.join(x)})" for x in uss])
    print(f"set {l}: {str_uss}")

输出：

set A: (3, 5), (2, 5), (5)
set B: 
set C: (2, 7)
set D: 
set E: (11), (2, 13), (13), (11, 13), (2, 11)
set F:

答案与您的建议有些不同，但对于您所描述的内容似乎是正确的。希望有帮助！

Answer 2

我最近编写了一个Python包，旨在有效地解决这个问题，唯一的区别是我有兴趣找到最小唯一的确定子集：https://github.com/alussana/TrieSUS

在我的研究过程中，我很惊讶没有找到这个算法问题的名称，而且我只能找到涉及枚举和比较幂集以找到每个集合的解决方案的蛮力方法 - 这是非常低效的，并且当考虑不存在解的集合时特别慢。

我的算法使用 trie 数据结构和一系列线性时间运算，首先大大减小问题规模，然后将其转化为相当于 集合覆盖问题，其解是使用 OR 提取的-Tools 的约束编程求解器。有关算法及其性能的更多信息可以在存储库中找到。

Answer 3

您可以使用此方法来实现。我写了一些方法来检查是否是字符串集的子集。

public boolean isASubset( Set<String> parent,Set<String> child) {

    boolean[] result = new boolean[1];
    child.forEach((String s) -> {
                if (!parent.contains(s)) {
                    result[0] = true;
                }
            }

    );

    return result[0];
}