title: Generate all binary words of length n
body: <p>For an algorithm I am currently implementing I need to handle a previous step I am not completely sure it is computationally tractable. This step requires to generate all binary words of length <code>n</code>, for an arbitrary <code>n</code> (it can be big, but in practice shouldn't be bigger than 50). If I remember well, this has exponential complexity (<code>O(2^n)</code>), which is no good.</p>
  
  <p>A naive recursive implementation might be the following:</p>
  
  <pre><code>def gen(n: Int, acc: List[String]) : List[String] = {
    if (n == 0) {
      acc
    } else {
      if (acc.length == 0) {
        gen(n - 1, List("0", "1"))
      } else {
        gen(n - 1, (for (i &lt;- acc) yield i ++ "0") ++ (for (j &lt;- acc) yield j ++ "1"))
      }
    }
  }
  gen(4, List())  //List(0000, 1000, 0100, 1100, 0010, 1010, 0110, 1110, 0001, 1001, 0101, 1101, 0011, 1011, 0111, 1111)
  </code></pre>
  
  <p>This works fine for small <code>n</code>'s and quickly freezes my computer as <code>n</code> increases.</p>
  
  <p>This problem can also be seen as obtaining the binary representation of all natural numbers <code>[0,2^n - 1]</code>, which can be easily parallelizable, but this does not work anyway for big values of <code>n</code>, since the number of elements is huge.</p>
  
  <p>Even if this were possible, another problem is that most data structures have a limit size (<code>Int.MaxValue</code> for most of them), but that is another story :)</p>
  
  <p>Does this problem actually have a solution?</p>