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

本文关键字：子集 集合 获取 迭代 | 更新日期: 2023-09-27 17:58:22

我知道迭代解决方案：

给定一组n元素

保存一个CCD_ 2并生成直到该CCD_。

但是如果n>32呢？

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

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

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

  2. ints/longs的阵列/ArrayList。具有类似于的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. BitArray。与上述相比，这可能不是一个非常有效的选择。

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

    10010 -> 10011
10011 -> 10100

请注意，这可能需要很长时间，因为子集太多了，但这不是问题所在。

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

您可以编写一个类似于这个简洁的Haskell实现：

powerSet = filterM (const [True, False])

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

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:罗塞塔代码提供了一个非递归实现：

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 }))));
}
相关文章：