Учитывая n, сгенерируйте все перестановки размером меньше 0,5n

Question

Учитывая целое число n, я хотел бы как можно эффективнее сгенерировать в вектор все перестановки целых чисел, размер которых меньше или равен 0.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

generate_half_perm (7) затем дает первый экземпляр этого сообщения. Я думаю , что этот код в настоящее время выше , O(2^(n/2).n)который является сложностью коды без одного необходимых для создания комбинаций combinations(1:half_n, l).

Мне было интересно, есть ли лучшая идея, которая может привести к более быстрому коду, учитывая, что мой n, вероятно, будет выше 100.

У меня была идея использовать этот код [Оптимальный способ вычисления перестановок в Джулии], но функция создания устарела и должна быть заменена в соответствии с этим другим ответом [Как заменить потребление и производство с каналами], и теперь это начинает усложняться для меня понимать!

Если алгоритмически у вас есть идея получше, без реализации 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]