Dado n, genere todas las permutaciones de tamaño menor que 0.5n

Question

Dado un número entero n, me gustaría generar en un vector, de la manera más eficiente posible, todas las permutaciones de números enteros de tamaño menor o igual que 0.5n.

Por ejemplo, para n=7eso sería:

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]

Mi idea actual es generar todas las permutaciones de tamaño kmenor que 0.5ny agregarlas:

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) luego da la primera instancia de esta publicación. Creo que este código está actualmente por encima de O(2^(n/2).n)cuál es la complejidad del código sin el necesario para generar las combinaciones combinations(1:half_n, l).

Me preguntaba si había alguna idea mejor que pudiera conducir a un código más rápido dado que mi n probablemente estará por encima de 100.

Tuve la idea de usar este código [Forma óptima de calcular permutaciones en Julia] pero la función de producción está en desuso y debería reemplazarse de acuerdo con esta otra respuesta [Cómo reemplazar consumir y producir con canales] y ahora eso comienza a complicarse para mí ¡comprender!

Si tiene una mejor idea algorítmicamente, sin la implementación de Julia, estaré encantado de probarla :)

pequeña edición: me doy cuenta de que lo que quería era:

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

Gracias a @Przemyslaw Szufel por hacerme encontrarlo :)

Answer 1

Para su valor "la mitad de N" igual a 3, esto sería:

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

Tenga en cuenta que esto no es una asignación, por lo que si desea ver el resultado, collectse requiere:

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]