得到一组特定的所有子集迭代

我知道迭代求解：得到一组特定的所有子集迭代

给定一组n元素

的

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

但是如果n> 32呢？

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

来源

2013-02-09 Elad Benda

有关使int数组，然后手动传播进位到一个INT到下一个是什么？像'[0000] [1111] - > [0001] [00]'顺便说一下，它会不会非常慢/不可能？ – biziclop 2013-02-09 12:16:27

使用'long'可以达到n = 64。如果n> 64，那么它将花费你的程序几个世纪来枚举所有的子集，所以你应该寻找一个解决方案来解决不涉及枚举子集的原始问题。 – 2013-02-09 12:49:32

为什么在这个世界上你想要这样做？这就像一个很长的循环...这是一个XY问题？ – thang 2013-02-09 13:15:40

如果您满意64项限制，您可以简单地使用long。

Array/ArrayList of int s/long s。有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

BitArray。与上述相比，可能不是一个非常有效的选择。

你可以有一个next功能，设置了至少显著位0到1，所有其余位为0。例如：
```
10010 -> 10011 
10011 -> 10100 
```

注意 - 这将可能采取永远，只是因为有这么很多子集，但这不是问题。除了没有内置filterM在C＃

powerSet = filterM (const [True, False])

：

来源

2013-02-09 12:55:10 Dukeling

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

来源

2013-02-09 12:43:40

你可以写这个简洁的Haskell实现的模拟。这没问题，你可以自己实现它。这是我在它的尝试：

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

来源

2013-02-09 13:31:43 Gebb

得到一组特定的所有子集迭代

回答

相关问题