ให้ n สร้างการเรียงสับเปลี่ยนทั้งหมดที่มีขนาดน้อยกว่า 0.5n

Question

ได้รับเลขจำนวนเต็มฉันต้องการที่จะสร้างเป็นเวกเตอร์ที่มีประสิทธิภาพที่สุดพีชคณิตทั้งหมดของจำนวนเต็มขนาดน้อยกว่าหรือเท่ากับn0.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

Gene_half_perm (7) จากนั้นให้อินสแตนซ์แรกของโพสต์นี้ ผมคิดว่ารหัสนี้ขณะนี้อยู่เหนือซึ่งเป็นความซับซ้อนของรหัสไม่หนึ่งที่จำเป็นในการสร้างรวมกันที่O(2^(n/2).n)combinations(1:half_n, l)

ฉันสงสัยว่ามีความคิดที่ดีกว่านี้หรือไม่ที่อาจนำไปสู่รหัสที่เร็วขึ้นเนื่องจาก n ของฉันน่าจะสูงกว่า 100

ฉันมีความคิดที่จะใช้รหัสนี้ [วิธีที่เหมาะสมที่สุดในการคำนวณการเรียงสับเปลี่ยนใน Julia]แต่ฟังก์ชันการผลิตถูกเลิกใช้และควรถูกแทนที่ด้วยคำตอบอื่นนี้[วิธีการแทนที่การบริโภคและการผลิตด้วยช่องทาง]และตอนนี้มันเริ่มซับซ้อนสำหรับฉัน เข้าใจไหม!

หากคุณมีความคิดที่ดีขึ้นตามอัลกอริทึมโดยไม่ต้องใช้ Julia ฉันยินดีที่จะลอง :)

การแก้ไขเล็กน้อย: ฉันตระหนักดีว่าสิ่งที่ฉันต้องการคือ:

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

ขอบคุณ @Przemyslaw Szufel ที่ทำให้ฉันพบ :)

Answer 1

สำหรับค่าของคุณ "ครึ่งหนึ่งของ N" เท่ากับ 3 สิ่งนี้จะเป็น:

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]