Diberikan n, buat semua permutasi dengan ukuran kurang dari 0,5n

Jan 08 2021

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=7itu 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 klebih kecil dari 0.5ndan 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

3 PrzemyslawSzufel Jan 08 2021 at 19:21

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 collectdiperlukan:

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]