Given an integer number n, I would like to generate into a vector, as efficiently as possible, all the permutations of integers of size lesser or equal than 0.5n.
For instance for n=7 that would be:
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]
My current idea is to generate all permutations of size k lesser than 0.5n and appending them:
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
generate_half_perm(7) then gives the first instance of this post. I think this code is currently above O(2^(n/2).n) which is the complexity of the code without the one needed to generate the combinations, combinations(1:half_n, l).
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.
I had the idea of using this code [Optimal way to compute permutations in Julia] but produce function is deprecated and should be replaced according with this other answer [How to replace consume and produce with channels] and now that starts to become complicated for me to understand!
If you have a better idea algorithmically, without the Julia implementation, I'll be glad to try it :)
small edit: I realize that what I wanted was:
collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))
Thanks to @Przemyslaw Szufel for made me find it :)