組合優化 - 枚舉包含給定集合的所有子集

給定一組集合S = {s1，s2，s3 ..}和一組元素X = {x1，x2，x3 ..}我怎樣才能枚舉所有設置Y其中一組Y的元素是從的提請與替換，以及X是一套Y.右聯盟的一個子集，這裏是我迄今爲止（蟒蛇）：組合優化 - 枚舉包含給定集合的所有子集

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的可能元素分支，是否有更好的方法來做到這一點？

來源

2013-07-12 qwwqwwq

因此，您基本上需要P（S）的一些子集，以便工會包含X. – jozefg

是的，我想優化所有此類子集的成本函數 – qwwqwwq

您的成本函數是什麼？ –

這個怎麼樣

# 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)我們必須遍歷冪2^n和執行n工會（固定時間）+ X的查詢，看是否X是套。

來源

2013-07-12 20:23:37 jozefg

組合優化 - 枚舉包含給定集合的所有子集

回答

相關問題