N verildiğinde, 0.5n'den küçük boyuttaki tüm permütasyonları oluştur

Question

Bir tam sayı verildiğinde n, olabildiğince verimli bir şekilde bir vektöre eşit veya daha küçük boyutlu tam sayıların tüm permütasyonlarını üretmek istiyorum 0.5n.

Örneğin n=7bunun için şunlar olabilir:

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]

Şu anki fikrim, kdaha küçük boyuttaki tüm permütasyonları oluşturmak 0.5nve bunları eklemek:

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) daha sonra bu yazının ilk örneğini verir. Sanırım bu kod, O(2^(n/2).n)kombinasyonları oluşturmak için gerekli olan olmadan kodun karmaşıklığı olan şu anda yukarıda combinations(1:half_n, l).

Benim n değerimin muhtemelen 100'ün üzerinde olacağı düşünüldüğünde daha hızlı bir koda yol açabilecek daha iyi bir fikir olup olmadığını merak ediyordum.

Bu kodu kullanma fikrim vardı [Julia'da permütasyonları hesaplamanın en uygun yolu], ancak işlev üretme artık kullanılmıyor ve şu diğer yanıta göre değiştirilmeli [Tüket ve üret kanallarla nasıl değiştirilir] ve şimdi bu benim için karmaşık hale geliyor anlamak!

Julia uygulaması olmadan algoritmik olarak daha iyi bir fikriniz varsa, denemekten memnuniyet duyarım :)

küçük düzenleme: İstediğimin şu olduğunun farkındayım:

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

@ Przemyslaw Szufel sayesinde bulmamı sağladı :)

Answer 1

3'e eşit olan "N'nin yarısı" değeriniz için bu şöyle olur:

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

Bunun ayırma olmadığını unutmayın, bu nedenle sonucu görmek istiyorsanız collectgereklidir:

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]