nが与えられると、0.5n未満のサイズのすべての順列を生成します

Jan 08 2021

整数が与えられた場合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で順列を計算する最適な方法]が、produce関数は非推奨であり、この他の回答[consumeとproduceをチャネルに置き換える方法]に従って置き換える必要があります。理解する!

Juliaを実装せずに、アルゴリズム的に優れたアイデアがあれば、ぜひ試してみてください:)

小さな編集:私が欲しかったのは:

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

@PrzemyslawSzufelに感謝します:)

回答

3 PrzemyslawSzufel Jan 08 2021 at 19:21

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]