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)은이 게시물의 첫 번째 인스턴스를 제공합니다. 이 코드는 현재 O(2^(n/2).n)조합을 생성하는 데 필요한 코드가없는 코드의 복잡성 인 combinations(1:half_n, l).

내 n이 100을 넘을 가능성이 있다는 점을 감안할 때 더 빠른 코드로 이어질 수있는 더 나은 아이디어가 있는지 궁금합니다.

나는 이 코드 를 사용하는 아이디어를 가지고 있었다 [줄리아에서 순열을 계산하는 최적의 방법] 그러나 생산 함수는 더 이상 사용되지 않으며 다른 답변 [소비 및 생산을 채널로 대체하는 방법] 에 따라 대체되어야 하며 이제는 복잡해지기 시작합니다. 이해하다!

Julia 구현없이 알고리즘 적으로 더 나은 아이디어가 있다면 기꺼이 시도해 볼 것입니다. :)

작은 편집 : 내가 원했던 것이 다음과 같음을 깨달았습니다.

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

@Przemyslaw Szufel에게 감사드립니다.

Answer 1

3과 같은 "N의 절반"값은 다음과 같습니다.

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]