nが与えられると、0.5n未満のサイズのすべての順列を生成します
整数が与えられた場合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
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]