Diberikan n, buat semua permutasi dengan ukuran kurang dari 0,5n
Diberikan bilangan bulat n
, saya ingin menghasilkan ke dalam vektor, seefisien mungkin, semua permutasi bilangan bulat dengan ukuran lebih kecil atau sama dari 0.5n
.
Misalnya untuk n=7
itu adalah:
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]
Ide saya saat ini adalah menghasilkan semua permutasi dengan ukuran k
lebih kecil dari 0.5n
dan menambahkannya:
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) kemudian memberikan contoh pertama dari posting ini. Saya pikir kode ini saat ini di atas O(2^(n/2).n)
yang merupakan kompleksitas kode tanpa yang diperlukan untuk menghasilkan kombinasi , combinations(1:half_n, l)
.
Saya bertanya-tanya apakah ada ide yang lebih baik yang dapat menghasilkan kode yang lebih cepat mengingat n saya kemungkinan besar di atas 100.
Saya punya ide untuk menggunakan kode ini [Cara optimal untuk menghitung permutasi di Julia] tetapi fungsi produksi sudah tidak digunakan lagi dan harus diganti sesuai dengan jawaban lain ini [Cara mengganti konsumsi dan produksi dengan saluran] dan sekarang hal itu mulai menjadi rumit bagi saya untuk mengerti!
Jika Anda memiliki ide yang lebih baik secara algoritme, tanpa penerapan Julia, saya akan dengan senang hati mencobanya :)
edit kecil: Saya menyadari bahwa yang saya inginkan adalah:
collect(Iterators.flatten(permutations.(powerset(1:7,0, floor(Int, 7/2)))))
Terima kasih kepada @Przemyslaw Szufel karena telah membuat saya menemukannya :)
Jawaban
Untuk nilai Anda "setengah dari N" sama dengan 3 ini akan menjadi:
using Combinatorics
Iterators.flatten(permutations.(powerset(1:3,1)))
Perhatikan bahwa ini non-alokasi jadi jika Anda ingin melihat hasilnya collect
diperlukan:
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]