Biorąc pod uwagę n, wygeneruj wszystkie permutacje o rozmiarze mniejszym niż 0,5n

Jan 08 2021

Biorąc pod uwagę liczbę całkowitą n, chciałbym wygenerować w wektorze, tak wydajnie, jak to możliwe, wszystkie permutacje liczb całkowitych o rozmiarze mniejszym lub równym 0.5n.

Na przykład n=7byłoby to:

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]

Mój obecny pomysł polega na wygenerowaniu wszystkich permutacji o rozmiarze kmniejszym niż 0.5ni dołączenie ich:

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

Następnie generuj_half_perm (7) podaje pierwsze wystąpienie tego postu. Myślę, że ten kod jest obecnie powyżej O(2^(n/2).n)którego jest złożoność kodu bez jednego potrzebnego do generowania kombinacji combinations(1:half_n, l).

Zastanawiałem się, czy istnieje lepszy pomysł, który może prowadzić do szybszego kodu, biorąc pod uwagę, że moje n prawdopodobnie będzie powyżej 100.

Wpadłem na pomysł, aby użyć tego kodu [Optymalny sposób obliczania permutacji w Julii], ale funkcja produkcji jest przestarzała i powinna zostać zastąpiona inną odpowiedzią [Jak zamienić konsumowanie i produkcję na kanały] i teraz zaczyna się to dla mnie komplikować rozumieć!

Jeśli masz lepszy pomysł algorytmicznie, bez implementacji Julii, z przyjemnością go wypróbuję :)

mała edycja: zdaję sobie sprawę, że chciałem:

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

Podziękowania dla @Przemyslaw Szufel za to, że go znalazłem :)

Odpowiedzi

3 PrzemyslawSzufel Jan 08 2021 at 19:21

Dla Twojej wartości „połowa N” równej 3 będzie to:

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

Zwróć uwagę, że nie jest to alokacja, więc jeśli chcesz zobaczyć wynik, musisz 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]