从集合列表中删除适当的子集

2024-03-28 12:15:20 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图从集合列表中删除所有正确的子集。在我的脑海中,我正在考虑使用2个for循环来检查一个元素是否是所有元素的适当子集,但是,这太慢了。你知道吗

我想的代码是:

设A为集合列表

设B为空列表

for elm in A:
    for i in range(len(A)):
        if elm.issubset(A[i]) and elm != A[i]:
            B.append(elm)
for junk in B:
    A.remove(junk)

我看了一些答案,看到了这个帖子: Efficient algorithm for finding all maximal subsets 这对去掉所有的子集都有效,但是当有两个相同的集合时,我遇到了一个问题,因为两个相等的集合是彼此的子集。如果两个集合是相同的,那么它就去掉了这两个集合,这就是为什么我想只去掉适当的子集而不是所有的子集。你知道吗


Tags: and代码in元素列表forlenif
1条回答
网友
1楼 · 发布于 2024-03-28 12:15:20

听起来像是动态规划的作业。所以我不会在代码中给出最终的解决方案。相反,我会给你一些提示。你知道吗

将列表长度A表示为N。想象一个1和0的NN矩阵,表示为X。如果X(i, j)是1,则表示A[i]A[j]的适当子集,否则为0。你的任务是用最小的工作量填满整个矩阵。你知道吗

您可以对矩阵X进行几种推断:

  1. X(i, j) == 1意味着X(j, i) == 0
  2. len(A[i]) >= len(A[j])意味着X(i, j) == 0
  3. X(i, j) == 1 and X(j, k) == 1意味着X(i, k) == 1

在设计算法时,您的任务是对比较进行排序,使填充X所需的平均比较次数最少,主要是尽可能多地使用上述规则。你知道吗

相关问题 更多 >