给定 n，生成大小小于 0.5n 的所有排列

Question

给定一个整数 n，我想尽可能高效地将大小小于或等于 0.5n 的整数的所有排列生成一个向量。

例如 n=7 将是：

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]

我目前的想法是生成大小 k 小于 0.5n 的所有排列并附加它们：

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) 然后给出这个 post 的第一个实例。我认为这段代码目前在 O(2^(n/2).n) 以上，这是没有生成组合所需的代码的复杂性 combinations(1:half_n, l).

我想知道是否有更好的想法可能会导致更快的代码，因为我的 n 可能会超过 100。

我有使用 but produce function is deprecated and should be replaced according with this other answer [How to replace consume and produce with channels] 的想法，但现在开始变得难以理解！

如果您在算法上有更好的想法，没有 Julia 实现，我很乐意尝试:)

小编辑：我意识到我想要的是：

collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))

感谢@Przemyslaw Szufel 让我找到它:)

Answer 1

如果您的值“N 的一半”等于 3，则为：

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

请注意，这是非分配的，因此如果您想查看结果，则需要 collect：

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]

给定 n，生成大小小于 0.5n 的所有排列

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

arrays

algorithm

optimization

permutation

julia