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

我有一个子集算法，可以找到给定集合的所有子集。原始集的东西是它是一个不断增长的集合，如果元素被添加到它，我需要重新计算它的子集。算法：如何在添加新元素时查找集合的子集？

有没有一种方法可以优化可以重新计算上一个计算点的子集的子集算法，而不是一次又一次地计算整个事物。

 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

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

回答

相关问题