我试图从集合列表中删除所有正确的子集。在我的脑海中,我正在考虑使用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 这对去掉所有的子集都有效,但是当有两个相同的集合时,我遇到了一个问题,因为两个相等的集合是彼此的子集。如果两个集合是相同的,那么它就去掉了这两个集合,这就是为什么我想只去掉适当的子集而不是所有的子集。你知道吗
听起来像是动态规划的作业。所以我不会在代码中给出最终的解决方案。相反,我会给你一些提示。你知道吗
将列表长度
A
表示为N
。想象一个1和0的N
乘N
矩阵,表示为X
。如果X(i, j)
是1,则表示A[i]
是A[j]
的适当子集,否则为0。你的任务是用最小的工作量填满整个矩阵。你知道吗您可以对矩阵
X
进行几种推断:X(i, j) == 1
意味着X(j, i) == 0
len(A[i]) >= len(A[j])
意味着X(i, j) == 0
X(i, j) == 1 and X(j, k) == 1
意味着X(i, k) == 1
在设计算法时,您的任务是对比较进行排序,使填充
X
所需的平均比较次数最少,主要是尽可能多地使用上述规则。你知道吗相关问题 更多 >
编程相关推荐