Bei n werden alle Permutationen mit einer Größe von weniger als 0,5 n erzeugt

Jan 08 2021

Bei einer gegebenen ganzen Zahl nmöchte ich alle Permutationen von ganzen Zahlen mit einer Größe kleiner oder gleich kleiner so effizient wie möglich in einen Vektor erzeugen 0.5n.

Zum Beispiel n=7wäre das:

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]

Meine aktuelle Idee ist es, alle Permutationen mit einer Größe zu generieren, die kkleiner als ist, 0.5nund sie anzuhängen:

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) gibt dann die erste Instanz dieses Beitrags an. Ich denke, dieser Code liegt derzeit über O(2^(n/2).n)der Komplexität des Codes, ohne den, der zum Generieren der Kombinationen benötigt wird combinations(1:half_n, l).

Ich habe mich gefragt, ob es eine bessere Idee gibt, die zu einem schnelleren Code führen könnte, da mein n wahrscheinlich über 100 liegen wird.

Ich hatte die Idee, mit diesen Code [Optimal Art und Weise zu berechnen Permutationen in Julia] aber produzieren Funktion ist veraltet und sollte nach dieser ersetzt werden andere Antwort [Wie ersetzen konsumieren und produzieren mit Kanälen] und jetzt, da beginnt für mich kompliziert werden verstehen!

Wenn Sie algorithmisch eine bessere Idee haben, ohne die Julia-Implementierung, werde ich es gerne versuchen :)

kleine Bearbeitung: Mir ist klar, dass ich Folgendes wollte:

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

Vielen Dank an @Przemyslaw Szufel, dass ich es gefunden habe :)

Antworten

3 PrzemyslawSzufel Jan 08 2021 at 19:21

Für Ihren Wert "Hälfte von N" gleich 3 wäre dies:

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

Beachten Sie, dass dies nicht zugeordnet ist. Wenn Sie also das Ergebnis sehen möchten, collectist Folgendes erforderlich:

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]