IEnumerable <T>のすべてのサブコレクションを生成できますか？私は何を意味

Question

は私が

{ 1, 2, 3 } 

のようなセットを持っている場合、すべてのサブセットがセットのサイズ3を持っているので、それらの2^3ある

{ }, 
{ 1 }, 
{ 2 }, 
{ 3 }, 
{ 1, 2 }, 
{ 2, 3 }, 
{ 1, 3 }, 
{ 1, 2, 3 } 

であるということです。私が思うどんな解決策も、サイズがn - 1までの以前のサブセットを「覚えている」必要があります。ここで、nはセットの長さです。例えば、私はそれはそれはsourceが配列に合うことができると仮定し、そしてHashSetが前のサブコレクションを保持できることを前提としてどのように

public static IEnumerable<IEnumerable<T>> AllSubcollections<T>(this IEnumerable<T> source) 
    { 
     // The empty set is always a subcollection 
     yield return new List<T>() { }; 

     T[] arr = source.ToArray(); 
     IEnumerable<int> indices = Enumerable.Range(0, arr.Length); 
     var last = new List<HashSet<int>>(new List<HashSet<int>>() { new HashSet<int>() }); 
     for(int k = 1; k < arr.Length; ++k) 
     { 
      var next = new List<HashSet<int>>(new List<HashSet<int>>()); 
      foreach(HashSet<int> hs in last) 
      { 
       foreach(int index in indices) 
       { 
        if(!hs.Contains(index)) 
        { 
         var addition = hs.Concat(new List<int> { index }); 
         yield return addition.Select(i => arr[i]); 
         next.Add(new HashSet<int>(addition)); 
        } 
       } 
      } 
     } 
    } 

お知らせのように見える書いたソリューションを持っています。

IEnumerable<T>はyieldであり、任意の数の結果（無限の場合もあります）がある場合、サブセットの問題に対してこれを行う解を書くことは可能でしょうか？

Answer 1

あなたはあなたの質問に欠陥を指摘します。アーカイブで終了しないIEnumerableがあります。

実際には、列挙子を慎重に記述して別のIEnumerableを返すようにしても、これは可能です。ソースがそれほど問題ではない場合、これは終了しません。 10億行のすべてのサブセットは、とにかく長く実行されるので、おそらくそれを打つことはありませんOutOfMemoryException。 C.McCoyIV @

public static IEnumerable<IReadOnlyList<T>> AllSubcollections<T>(this IEnumerable<T> source) 
{ 
    // The empty set is always a subcollection 
    yield return new List<T>() { }; 

    List<T> priors = new List<T>(); 
    List<bool> includes = new List<bool>(); // Need a bitvector to get past 64 elements. 
    while (source.MoveNext()) 
    { 
     for (int i = 0; i < includes.Count; ++i) 
      includes[i] = false; 
     // Always return the newest item in any set. This avoids dupes. 
     priors.Add(source.Current); 
     priors.Add(true); 

     bool breakout; 
     do { 
      List<T> set = new List<T>(); 
      for (int i = 0; i < priors.Count; ++i) 
       if (includes[i]) 
        set[i] = includes[i]; 
      yield return (IReadOnlyList<T>)set; 

      // Bitvector increment 
      breakout = true; 
      for (int i = 0; i < priors.Count; ++i) { 
       if (!includes[i]) { 
        for (int j = 0; j < i; ++j) 
         includes[j] = 0; 
        includes[i] = true; 
        breakout = false; 
        break; 
       } 
      } 
     } while (!breakout);    
    } 
}