算法:添加新元素时如何找到集合的子集？

Question

我有一个子集算法，可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合，如果向其中添加元素，我需要再次重新计算它的子集。

有没有一种方法可以优化子集算法，该算法可以从最后一个计算点重新计算子集，而不是一次又一次地计算整个事情。

        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;
        }

Answer 1

当然你只需要将相同的算法应用于每个先前生成的元素到额外的集合(只有增长的部分)

例如:

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

你的集合从 a1a2a3 增长到 a1a2a3a4a5

你需要迭代子集到额外添加的集合:

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

顺便说一句 我看到你添加了动态编程标签，但我认为这不是 dp 问题，因为 dp 主要用于需要最大化/最小化/计算子集的问题，但不是自己生成子集。