title: C data structure to mimic C#'s List<List<int>>?
body: <p>I am looking to refactor a c# method into a c function in an attempt to gain some speed, and then call the c dll in c# to allow my program to use the functionality.</p>
  
  <p>Currently the c# method takes a list of integers and returns a list of lists of integers.  The method calculated the power set of the integers so an input of 3 ints would produce the following output (at this stage the values of the ints is not important as it is used as an internal weighting value)</p>
  
  <pre><code>1
  2
  3
  1,2
  1,3
  2,3
  1,2,3
  </code></pre>
  
  <p>Where each line represents a list of integers.  The output indicates the index (with an offset of 1) of the first list, not the value.  So 1,2 indicates that the element at index 0 and 1 are an element of the power set.</p>
  
  <p>I am unfamiliar with c, so what are my best options for data structures that will allow the c# to access the returned data?</p>
  
  <p>Thanks in advance</p>
  
  <p><strong>Update</strong></p>
  
  <p>Thank you all for your comments so far. Here is a bit of a background to the nature of the problem.</p>
  
  <p>The iterative method for calculating the power set of a set is fairly straight forward.  Two loops and a bit of bit manipulation is all there is to it really.  It just get called..a lot (in fact billions of times if the size of the set is big enough).</p>
  
  <p>My thoughs around using c (c++ as people have pointed out) are that it gives more scope for performance tuning.  A direct port may not offer any increase, but it opens the way for more involved methods to get a bit more speed out of it.  Even a small increase per iteration would equate to a measurable increase.</p>
  
  <p>My idea was to port a direct version and then work to increase it.  And then refactor it over time (with help from everyone here at SO).</p>
  
  <p><strong>Update 2</strong></p>
  
  <p>Another fair point from jalf, I dont have to use list or equivelent.  If there is a better way then I am open to suggestions.  The only reason for the list was that each set of results is not the same size.</p>
  
  <p><strong>The code so far...</strong></p>
  
  <pre><code>public List&lt;List&lt;int&gt;&gt; powerset(List&lt;int&gt; currentGroupList)
  {
      _currentGroupList = currentGroupList;
      int max;
      int count;
  
      //Count the objects in the group
      count = _currentGroupList.Count;
      max = (int)Math.Pow(2, count);
  
      //outer loop
      for (int i = 0; i &lt; max; i++)
      {
          _currentSet = new List&lt;int&gt;();
  
          //inner loop
          for (int j = 0; j &lt; count; j++)
          {              
              if ((i &amp; (1 &lt;&lt; j)) == 0)
              {
                  _currentSetList.Add(_currentGroupList.ElementAt(j));                          
              }
          }
          outputList.Add(_currentSetList);
      }   
      return outputList;
  }
  </code></pre>
  
  <p>As you can see, not a lot to it.  It just goes round and round a lot!</p>
  
  <p>I accept that the creating and building of lists may not be the most efficient way, but I need some way of providing the results back in a manageable way.</p>
  
  <p><strong>Update 2</strong></p>
  
  <p>Thanks for all the input and implementation work.  Just to clarify a couple of points raised: I dont need the output to be in 'natural order', and also I am not that interested in the empty set being returned. </p>
  
  <p>hughdbrown's implementation is intesting but i think that i will need to store the results (or at least a subset of them) at some point.  It sounds like memory limitiations will apply long before running time becomes a real issue.
  Partly because of this, I think I can get away with using bytes instead of integers, giving more potential storage.</p>
  
  <p>The question really is then:  Have we reached the maximum speed for this calcualtion in C#?  Does the option of unmanaged code provide any more scope.  I know in many respects the answer is futile, as even if we havled the time to run, it would only allow an extra values in the original set.</p>