Given n, generate all permutations of size lesser than 0.5n

Viewed 100

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 :)

1 Answers

For your value "half of N" equal to 3 this would be:

using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))

Note that this is non-allocating so if you want to see the result collect is required:

julia> collect(Iterators.flatten(permutations.(powerset(1:3,1))))
15-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [2, 3]
 [3, 2]
 [1, 2, 3]
 [1, 3, 2]
 [2, 1, 3]
 [2, 3, 1]
 [3, 1, 2]
 [3, 2, 1]
Related