算法：如何在添加新元素時查找集合的子集？

我有一個子集算法，可以找到給定集合的所有子集。原始集的東西是它是一個不斷增長的集合，如果元素被添加到它，我需要重新計算它的子集。算法：如何在添加新元素時查找集合的子集？

有沒有一種方法可以優化可以重新計算上一個計算點的子集的子集算法，而不是一次又一次地計算整個事物。

 public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source) 
     { 
      if (!source.Any()) 
       return Enumerable.Repeat(Enumerable.Empty<T>(), 1); 

      var element = source.Take(1); 

      var haveNots = SubSetsOf(source.Skip(1)); 
      var haves = haveNots.Select(set => element.Concat(set)); 

      return haves.Concat(haveNots); 
     } 

     private static bool Valid(IEnumerable<int> set) 
     { 
      bool flag = false; 

      foreach (var element in set) 
      { 
       var f = element > 0; 
       if (f == flag) 
       { 
        return false; 
       } 

       flag = f; 
      } 

      return true; 
     }

來源

2017-06-22 Vishal Anand

添加元素時獲得的唯一新子集是那些包含它的元素，因此如果您在添加元素e之前已知道所有子集的集合C，則將「S union e」添加到每個子集S的集合中在C. –

當然你只需要相同的算法應用到每個先前生成的元素的額外集（僅增長部分）

例：

如果生成的子集是s1, s2, ... , sn

和您的設置從a1a2a3增長到a1a2a3a4a5

您需要迭代ove [R子集的額外增加一套：

for set x in subsets do : 
    generate(x) 
     generate(x + a4) 
     generate(x + a5)

順便說一句我看你添加動態編程標籤，但我不認爲這是一個DP問題，因爲DP主要用於需要最大化問題/最小化/計數子集，但不生成他們自己的子集。

來源

2017-06-22 11:01:25

算法：如何在添加新元素時查找集合的子集？

回答

相關問題