Dado n, gere todas as permutações de tamanho menor que 0,5n

Question

Dado um número inteiro n, gostaria de gerar em um vetor, da forma mais eficiente possível, todas as permutações de inteiros de tamanho menor ou igual a 0.5n.

Por exemplo, para n=7isso seria:

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]

Minha ideia atual é gerar todas as permutações de tamanho kmenor 0.5ne anexá-las:

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) então dá a primeira instância deste post. Acho que esse código está acima do O(2^(n/2).n)qual é a complexidade do código sem o necessário para gerar as combinações combinations(1:half_n, l),.

Gostaria de saber se há alguma ideia melhor que possa levar a um código mais rápido, visto que meu n provavelmente estará acima de 100.

Tive a ideia de usar este código [Forma ideal de calcular permutações em Julia] mas a função de produção está obsoleta e deve ser substituída de acordo com esta outra resposta [Como substituir consumir e produzir por canais] e agora isso começa a se tornar complicado para mim para entender!

Se você tiver uma ideia melhor algoritmicamente, sem a implementação de Julia, terei o maior prazer em experimentá-la :)

pequena edição: percebo que o que eu queria era:

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

Obrigado a @Przemyslaw Szufel por me fazer encontrá-lo :)

Answer 1

Para o seu valor "metade de N" igual a 3, isso seria:

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

Observe que isso não é alocação, portanto, se você quiser ver o resultado, collecté necessário:

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]