c# - 迭代地获取特定集合的所有子集

Question

我知道迭代解决方案：

给定一组n元素

保存int v = 2^n 并生成所有二进制数v。

但是如果 n > 32 怎么办？

我知道它已经是 2^32 个子集，但是 - 绕过 32 个元素限制的方法是什么？

Answer 1

1. 如果您对 64 项限制感到满意，您可以简单地使用long.

2. 数组 /ArrayList的ints / longs。有一个next类似的功能：

   bool next(uint[] arr)
     for (int i = 0; i < arr.length; i++)
       if (arr[i] == 2^n-1) // 11111 -> 00000
         arr[i] = 0
       else
         arr[i]++
         return true
     return false // reached the end -> there is no next
   

3. 位数组。与上述相比，可能不是一个非常有效的选择。

   您可以使用一个next函数将最低有效位 0 设置为 1，并将所有剩余位设置为 0。例如：

   10010 -> 10011
   10011 -> 10100
   

注意 - 这可能会永远持续下去，仅仅是因为有这么多的子集，但这不是问题所在。

Answer 2

您可以使用@biziclop 方法，通过以下方式传播进位位：将您的数字存储为长度为 K 的 32 位“数字”向量。因此，您可以生成 2^(K*32) 个子集，并且每个增量操作最多需要 O(K) 次操作。我能想到的另一件事是递归回溯，它将在一个数组中生成所有子集。

Answer 3

您可以编写这个简洁的 Haskell 实现的模拟：

powerSet = filterM (const [True, False])

filterM除了C#中没有内置的。没问题，你可以自己实现。这是我的尝试：

public static IEnumerable<IEnumerable<T>> PowerSet<T>(IEnumerable<T> els)
{
    return FilterM(_ => new[] {true, false}, els);
}

public static IEnumerable<IEnumerable<T>> FilterM<T>(
    Func<T, IEnumerable<bool>> p,
    IEnumerable<T> els)
{
    var en = els.GetEnumerator();
    if (!en.MoveNext())
    {
        yield return Enumerable.Empty<T>();
        yield break;
    }

    T el = en.Current;
    IEnumerable<T> tail = els.Skip(1);
    foreach (var x in
        from flg in p(el)
        from ys in FilterM(p, tail)
        select flg ? new[] { el }.Concat(ys) : ys)
    {
        yield return x;
    }
}

然后你可以像这样使用它：

foreach (IEnumerable<int> subset in PowerSet(new [] { 1, 2, 3, 4 }))
{
    Console.WriteLine("'{0}'", string.Join(",", subset));
}

如您所见，在实现中的任何地方都没有int也没有long明确使用，所以这里的真正限制是当前堆栈大小限制可达到的最大递归深度。

UPD： Rosetta Code提供了非递归实现：

public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(IEnumerable<T> input)
{
    var seed = new List<IEnumerable<T>>() { Enumerable.Empty<T>() }
        as IEnumerable<IEnumerable<T>>;

    return input.Aggregate(seed, (a, b) =>
        a.Concat(a.Select(x => x.Concat(new List<T> { b }))));
}