title: Given n, generate all permutations of size lesser than 0.5n
body: <p>Given an integer number <code>n</code>, I would like to generate into a vector, as efficiently as possible, all the permutations of integers of size lesser or equal than <code>0.5n</code>.</p>
  <p>For instance for <code>n=7</code> that would be:</p>
  <pre><code>15-element Array{Array{Int64,1},1}:
   [1]
   [2]
   [3]
   [1, 2]
   [1, 3]
   [2, 1]
   [2, 3]
   [3, 1]
   [3, 2]
   [1, 2, 3]
   [1, 3, 2]
   [2, 1, 3]
   [2, 3, 1]
   [3, 1, 2]
   [3, 2, 1]
  </code></pre>
  <p>My current idea is to generate all permutations of size <code>k</code> lesser than <code>0.5n</code> and appending them:</p>
  <pre><code>using Combinatorics
  
  function generate_half_perm(n)
      half_n = floor(Int, n/2)
      result = []
      for l in 1:half_n
              for c in permutations(1:half_n, l)
                      push!(result, c)
              end
      end
      return result
  end
  </code></pre>
  <p>generate_half_perm(7) then gives the first instance of this post. I think this code is currently above <code>O(2^(n/2).n)</code> which is the complexity of the code without the one needed to generate the combinations, <code>combinations(1:half_n, l)</code>.</p>
  <p>I was wondering if there was any better idea which may lead to a faster code given that my
  n will likely be above 100.</p>
  <p>I had the idea of using <a href="https://stackoverflow.com/a/31771435/10094437">this code [Optimal way to compute permutations in Julia]</a> but produce function is deprecated and should be replaced according with this <a href="https://discourse.julialang.org/t/how-to-replace-consume-and-produce-with-channels/5125/4" rel="nofollow noreferrer">other answer [How to replace consume and produce with channels]</a> and now that starts to become complicated for me to understand!</p>
  <p>If you have a better idea algorithmically, without the Julia implementation, I'll be glad to try it :)</p>
  <p>small edit: I realize that what I wanted was:</p>
  <pre><code>collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))
  </code></pre>
  <p>Thanks to @Przemyslaw Szufel for made me find it :)</p>