Dato n, genera tutte le permutazioni di dimensione inferiore a 0,5n

Question

Dato un numero intero n, vorrei generare in un vettore, nel modo più efficiente possibile, tutte le permutazioni di interi di dimensione minore o uguale a 0.5n.

Ad esempio, per n=7questo sarebbe:

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]

La mia idea attuale è quella di generare tutte le permutazioni di dimensione kinferiore a 0.5ne aggiungerle:

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) fornisce quindi la prima istanza di questo post. Penso che questo codice è attualmente al di sopra O(2^(n/2).n), che è la complessità del codice senza quella necessaria per generare le combinazioni, combinations(1:half_n, l).

Mi chiedevo se ci fosse un'idea migliore che potesse portare a un codice più veloce dato che il mio n sarà probabilmente superiore a 100.

Avevo l'idea di usare questo codice [Modo ottimale per calcolare le permutazioni in Julia] ma la funzione di produzione è deprecata e dovrebbe essere sostituita in base a quest'altra risposta [Come sostituire consuma e produce con i canali] e ora inizia a complicarsi per me capire!

Se hai un'idea migliore algoritmicamente, senza l'implementazione di Julia, sarò felice di provarla :)

piccola modifica: mi rendo conto che quello che volevo era:

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

Grazie a @Przemyslaw Szufel per avermi fatto trovare :)

Answer 1

Per il tuo valore "metà di N" uguale a 3, questo sarebbe:

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

Nota che questo non è allocativo, quindi se vuoi vedere il risultato collectè necessario:

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]