title: Generate all combinations for a list of strings
body: <p>I want to generate a list of all possible combinations of a list of strings (it's actually a list of objects, but for simplicity we'll use strings). I need this list so that I can test every possible combination in a unit test.</p>
  
  <p>So for example if I have a list of:</p>
  
  <pre><code>  var allValues = new List&lt;string&gt;() { "A1", "A2", "A3", "B1", "B2", "C1" }
  </code></pre>
  
  <p>I need a <code>List&lt;List&lt;string&gt;&gt;</code> with all combinations like:</p>
  
  <pre><code>  A1
    A2
    A3
    B1
    B2
    C1
    A1 A2
    A1 A2 A3
    A1 A2 A3 B1
    A1 A2 A3 B1 B2
    A1 A2 A3 B1 B2 C1
    A1 A3
    A1 A3 B1
    etc...
  </code></pre>
  
  <p>A recursive function is probably the way to do it to get all combinations, but it seems harder than I imagined.</p>
  
  <p>Any pointers?</p>
  
  <p>Thank you.</p>
  
  <p>EDIT: two solutions, with or without recursion:</p>
  
  <pre><code>public class CombinationGenerator&lt;T&gt;
  {
      public IEnumerable&lt;List&lt;T&gt;&gt; ProduceWithRecursion(List&lt;T&gt; allValues) 
      {
          for (var i = 0; i &lt; (1 &lt;&lt; allValues.Count); i++)
          {
              yield return ConstructSetFromBits(i).Select(n =&gt; allValues[n]).ToList();
          }
      }
  
      private IEnumerable&lt;int&gt; ConstructSetFromBits(int i)
      {
          var n = 0;
          for (; i != 0; i /= 2)
          {
              if ((i &amp; 1) != 0) yield return n;
              n++;
          }
      }
  
      public List&lt;List&lt;T&gt;&gt; ProduceWithoutRecursion(List&lt;T&gt; allValues)
      {
          var collection = new List&lt;List&lt;T&gt;&gt;();
          for (int counter = 0; counter &lt; (1 &lt;&lt; allValues.Count); ++counter)
          {
              List&lt;T&gt; combination = new List&lt;T&gt;();
              for (int i = 0; i &lt; allValues.Count; ++i)
              {
                  if ((counter &amp; (1 &lt;&lt; i)) == 0)
                      combination.Add(allValues[i]);
              }
  
              // do something with combination
              collection.Add(combination);
          }
          return collection;
      }
  }
  </code></pre>