title: Generate all combinations of a collection in o(1)
body: <p>Combinations of a collection of int {1,2,3} is:</p>
  
  <blockquote>
    <p>{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}</p>
  </blockquote>
  
  <p>The common solution is to track the representative bit-mask of a index.</p>
  
  <p>From my example for numbers in 0-7:</p>
  
  <blockquote>
    <p>000,001,010,011,100,101,110,111</p>
  </blockquote>
  
  <p>This algorithm allows an iterative solution, 
  each time the generator goes over each bit and decides whether insert the item or not,
  so it creates the next combination with a run-time of O(n). </p>
  
  <p>Gray codes:(From Wikipedia)
  The reflected binary code (RBC), also known as Gray code after Frank Gray, 
  is a binary numeral system where two successive values differ in only one bit</p>
  
  <p>If we just use gray numbers instead we get this range of numbers:</p>
  
  <blockquote>
    <p>000,001,011,010,110,111,101,100</p>
  </blockquote>
  
  <p>The result is the same in different order:</p>
  
  <blockquote>
    <p>{},{1},{1,2},{2},{2,3},{1,2,3},{1,3},{3}</p>
  </blockquote>
  
  <p>But here we see that the difference is only one item.
  Is it possible to implement the generator in O(1) using gray code range.</p>
  
  <p>I understand that the returned list will have a O(n) run-time anyway if iterated.</p>