0

给定一组集合 S = { s1, s2, s3 .. } 和一组元素 X = { x1, x2, x3 .. } 我如何枚举所有集合 Y，其中集合 Y 的元素是从 S 中提取的替换，并且 X 是集合 Y 的并集的子集。对，这是我到目前为止所拥有的（python）：

def enumerate_containing_subsets(S, X):
    if not set(X).issubset(set().union(*S)): return
    previous_generation = [[]]
    for element in X:
        current_generation = []
        for subset in S:
            if element in subset:
                for node in previous_generation:
                    current_generation.append( node + [subset] )
        previous_generation = current_generation
    return previous_generation

S = [ frozenset([1,2]), frozenset([3]), frozenset([4,1])]
X = [ 1, 2 ]
enumerate_containing_subsets(S, X)
>> [[frozenset([1, 2]), frozenset([1, 2])], 
    [frozenset([1, 4]), frozenset([1, 2])]]

这种天真的方法是O (n^n) 我认为，我基本上是在这里构建一棵树，并在每一代为包含下一个 X 值的 S 的每个可能元素进行分支，有没有更好的方法来做到这一点？

4

1 回答 1

1

这个怎么样

# Ruby
require 'set'
s = Set[Set[1, 2, 3, 4], Set[3, 4, 5], Set[1, 2, 3, 7, 8, 9]]
x = Set[1, 3, 4]

class Set
    def powerset 
        inject(Set[Set[]]) do |ps, item| 
            ps.union ps.map {|e| e.union (Set.new [item])}
        end
    end
end
pow = s.powerset
pow.select! { |sub|x <= sub.flatten }
p pow

这是O(n * x * 2^n)因为我们必须遍历 powerset2^n并执行nunions (constant time) + x 查询以查看 X 是否在集合中。

于 2013-07-12T20:23:37.680 回答