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

Question

我知道迭代求解：

給定一組n元素

的

保存int v = 2^n，並生成所有二進制數達此v。

但是如果n> 32呢？

我知道它已經是2^32個子集，但是 - 繞過32個元素限制的方法是什麼？

Answer 1

1. 如果您滿意64項限制，您可以簡單地使用long。

2. 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 
   

3. BitArray。與上述相比，可能不是一個非常有效的選擇。

   你可以有一個next功能，設置了至少顯著位0到1，所有其餘位爲0。例如：

   10010 -> 10011 
   10011 -> 10100 
   

注意 - 這將可能採取永遠，只是因爲有這麼很多子集，但這不是問題。除了沒有內置filterM在C＃

powerSet = filterM (const [True, False]) 

：

Answer 2

您可以使用@biziclop方式，通過以下列方式傳播進位：將您的號碼存儲爲長度爲K的32位「數字」的向量。因此，您可以生成2 ^（K * 32）個子集，並且每個增量操作最多將執行O（K）操作。 我能想到的另一件事是遞歸回溯，它將生成一個數組中的所有子集。

Answer 3

你可以寫這個簡潔的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 })))); 
}