Permutationen
Eine Permutation ist die Anordnung einer Menge von Objekten, bzw. die Änderung
einer Anordnung. Also zum Beispiel Kreis -- Dreieck -- Quadrat als eine erste Anordnung und Dreieck -- Quadrat -- Kreis als eine zweite Anordnung oder eine Permuation der ersten. Hier werden nur Anordnungen von jeweils unterschiedlichen Objekten betrachtet. Es gibt also keine Wiederholungen von Objekten.
Wie kann man alle Permutationen eine Menge von Objekten erhalten? Wenn die Menge n Objekte enthält, dann gibt es n! Permutationen, denn für die erste Stelle einer Anordnungen kann aus allen n Elementen ausgewählt werden, für die zweite Stelle stehen noch n - 1 Möglichkeiten zur Verfügung und so fort, bis schließlich an der letzten Stelle das einzige verbleibende Element eingesetzt werden muss.
quick and dirty
Die Funktion randperm(n) erzeugt eine zufällige Permutation. Lässt man nun eine große Zahl solcher zufälligen Permutationen erzeugen, wird man irgendwann alle möglichen Permutationen erhalten. Die Funktion unique entfernt alle Dopplungen in der übergebenen Menge.
julia> import Random: randperm
julia> unique([randperm(7) for i in 1:70000])
5040-element Array{Array{Int64,1},1}:
[4, 1, 3, 5, 2, 6, 7]
[6, 4, 2, 3, 7, 1, 5]
[3, 5, 7, 4, 6, 1, 2]
[3, 1, 4, 7, 5, 2, 6]
[6, 1, 3, 2, 7, 5, 4]
[1, 3, 2, 6, 4, 5, 7]
[5, 1, 3, 7, 2, 6, 4]
[5, 6, 2, 4, 3, 1, 7]
[1, 6, 5, 2, 3, 4, 7]
[5, 2, 6, 3, 7, 4, 1]
⋮
[2, 5, 4, 3, 1, 7, 6]
[2, 1, 5, 6, 7, 3, 4]
[5, 3, 6, 2, 7, 1, 4]
[5, 7, 3, 4, 1, 6, 2]
[4, 2, 5, 6, 7, 1, 3]
[2, 7, 6, 3, 1, 4, 5]
[4, 6, 5, 3, 2, 7, 1]
[1, 2, 3, 6, 7, 5, 4]
[2, 1, 7, 3, 6, 5, 4]
systematischer, kurz, aber teuer
Alle möglichen Anordnungen für Objekte erhält man (sicher) aus den Anordnungen von Objekten, indem man das neue Objekt an jede der möglichen Positionen plaziert. Mithilfe von boolschen Indexvektoren lässt sich das in Julia leicht implementieren.
function permset(n::Int)
if !(1 <= n <= 12)
error("`n` needs to be in the range 1:12")
elseif n == 1
return [[1]]
elseif n == 2
return [[2, 1], [1, 2]]
else
res = Vector{Vector{Int}}(undef, factorial(n))
k = 1 # index of res
for i in 1:n
ix = trues(n) # index vector
ix[i] = false
for p in permset(n-1)
res[k] = fill(n, n)
res[k][i] = n
res[k][ix] .= p
k += 1
end
end
end
res
end
res[k] wird an der Stelle auf den Wert gesetzt. Die übrigen
Stellen werden mit allen Permutationen für besetzt.
Beispiel:
permset(4)
24-element Array{Array{Int64,1},1}:
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 2, 3, 1]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 1, 2, 3]
[3, 4, 2, 1]
[3, 4, 1, 2]
[2, 4, 3, 1]
[1, 4, 3, 2]
[2, 4, 1, 3]
[1, 4, 2, 3]
[3, 2, 4, 1]
[3, 1, 4, 2]
[2, 3, 4, 1]
[1, 3, 4, 2]
[2, 1, 4, 3]
[1, 2, 4, 3]
[3, 2, 1, 4]
[3, 1, 2, 4]
[2, 3, 1, 4]
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
permset(9)
362880-element Array{Array{Int64,1},1}:
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 1, 2]
[9, 8, 7, 6, 5, 4, 2, 3, 1]
[9, 8, 7, 6, 5, 4, 1, 3, 2]
[9, 8, 7, 6, 5, 4, 2, 1, 3]
[9, 8, 7, 6, 5, 4, 1, 2, 3]
[9, 8, 7, 6, 5, 3, 4, 2, 1]
[9, 8, 7, 6, 5, 3, 4, 1, 2]
[9, 8, 7, 6, 5, 2, 4, 3, 1]
[9, 8, 7, 6, 5, 1, 4, 3, 2]
[9, 8, 7, 6, 5, 2, 4, 1, 3]
[9, 8, 7, 6, 5, 1, 4, 2, 3]
[9, 8, 7, 6, 5, 3, 2, 4, 1]
⋮
[3, 2, 4, 1, 5, 6, 7, 8, 9]
[3, 1, 4, 2, 5, 6, 7, 8, 9]
[2, 3, 4, 1, 5, 6, 7, 8, 9]
[1, 3, 4, 2, 5, 6, 7, 8, 9]
[2, 1, 4, 3, 5, 6, 7, 8, 9]
[1, 2, 4, 3, 5, 6, 7, 8, 9]
[3, 2, 1, 4, 5, 6, 7, 8, 9]
[3, 1, 2, 4, 5, 6, 7, 8, 9]
[2, 3, 1, 4, 5, 6, 7, 8, 9]
[1, 3, 2, 4, 5, 6, 7, 8, 9]
[2, 1, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Der Algorithmus ist nicht sehr effizient und schon für moderate Werte von wächst der Speicherbedarf sehr stark und erreicht schnell die Kapazitäten üblicher Hardware.
effizienter
Es lassen sich alle Permutationen durchlaufen, indem man in einem Schritt nur zwei Elemente vertauscht, also eine Transposition ausführt. Für n = 3 ist die Liste mit Permutationen mit den entsprechenden Transpositionen:
| [1, 2, 3] | |
| [1, 3, 2] | (2, 3) |
| [3, 1, 2] | (1, 2) |
| [3, 2, 1] | (2, 3) |
| [2, 3, 1] | (1, 2) |
| [2, 1, 3] | (2, 3) |
| [1, 2, 3] | (1, 2) |
Es genügt also, die jeweils nächste Transposition anzugeben. Dies kann man erreichen, indem man für jedes Element ein Julia-Objekt erzeugt, das die Transpositionen für das ihm zugeordnete Element ausgibt. So wandert beispielsweise die 1 von der ersten zur letzten Position, dann wandert die 2 eine Position weiter, usf.. Die Vorgehensweise verwendet die Schnittstelle für iterierbare Objekte.
Es enthält jeweils ein Julia-Objekt das nächste, das letzte Objekt in der Kette ist vom Typ PCountLeaf.
abstract type AbstractPCount end
mutable struct PCountLeaf <: AbstractPCount
n::Int # counter range: 1:n
count::Int
incr::Int # counting direction
end
Das allgemeine Objekt ist vom Typ PCount.
mutable struct PCount <: AbstractPCount
n::Int # counter range: 1:n
succ::AbstractPCount
count::Int
incr::Int # counting direction
end
Falls das zugeordnete Element an der ersten oder letzten Position ist, wird
jeweils der nächste Schritt des nächsten Objekts ausgeführt. Der Wert
von offset ergibt sich aus der Art und Weise, wie Transpositionen angegeben
werden. Die Ausgabe von 2 bedeutet, dass die Elemete an den Positionen 2 und 3
vertauscht werden sollen.
"""
iterate(p::PCount, state)
advance the counter
Return next value if `p` is not at it's boundaries,
otherwise reset `p` and call the counter at the next level.
"""
function Base.iterate(p::PCount, offset)
if 0 < p.count < p.n
valret = p.count
p.count += p.incr
# println("go: $(p.n), offset: $(offset)")
# offset is never passed to higher (towards top) levels
return (valret + offset, 0)
else
# `offset` is increased, if the position of the current counter is
# at it's minimum
offset += p.count == 0 ? 1 : 0
valsucc = iterate(p.succ, offset)
if valsucc != nothing
p.incr = -p.incr
p.count = p.incr > 0 ? 1 : p.n - 1
end
return valsucc
end
end
Es sind alle Permutationen durchlaufen, sobald alle zugeordneten Elemente wieder an der Ausgangsposition angelangt sind.
Damit lässt sich jetzt leicht eine Funktion schreiben, welche die Permutationen einer Anordnung von Elementen in v sehr effizient erzeugt.
function permset(v::T where T<:AbstractArray)
n = length(v)
res = Vector{Vector{eltype(v)}}(undef, factorial(n))
it = PCount(n)
k = 1
res[k] = copy(v)
k += 1
for i in it
v[[i, i+1]] = v[[i+1, i]]
res[k] = copy(v)
k += 1
end
res
end
julia> ps7 = permset([1, 2, 3, 5, 7, 11, 13])
5040-element Array{Array{Int64,1},1}:
[1, 2, 3, 5, 7, 11, 13]
[2, 1, 3, 5, 7, 11, 13]
[2, 3, 1, 5, 7, 11, 13]
[2, 3, 5, 1, 7, 11, 13]
[2, 3, 5, 7, 1, 11, 13]
[2, 3, 5, 7, 11, 1, 13]
[2, 3, 5, 7, 11, 13, 1]
[3, 2, 5, 7, 11, 13, 1]
⋮
[2, 3, 5, 7, 13, 11, 1]
[2, 3, 5, 7, 13, 1, 11]
[2, 3, 5, 7, 1, 13, 11]
[2, 3, 5, 1, 7, 13, 11]
[2, 3, 1, 5, 7, 13, 11]
[2, 1, 3, 5, 7, 13, 11]
[1, 2, 3, 5, 7, 13, 11]
julia> sort(ps7)
5040-element Array{Array{Int64,1},1}:
[1, 2, 3, 5, 7, 11, 13]
[1, 2, 3, 5, 7, 13, 11]
[1, 2, 3, 5, 11, 7, 13]
[1, 2, 3, 5, 11, 13, 7]
[1, 2, 3, 5, 13, 7, 11]
[1, 2, 3, 5, 13, 11, 7]
[1, 2, 3, 7, 5, 11, 13]
[1, 2, 3, 7, 5, 13, 11]
⋮
[13, 11, 7, 3, 5, 2, 1]
[13, 11, 7, 5, 1, 2, 3]
[13, 11, 7, 5, 1, 3, 2]
[13, 11, 7, 5, 2, 1, 3]
[13, 11, 7, 5, 2, 3, 1]
[13, 11, 7, 5, 3, 1, 2]
[13, 11, 7, 5, 3, 2, 1]
Alternativ kann man durch eine veränderte Version von permset
die Permutationen nur ausgeben, anstatt einen Vektor zu befüllen, oder ein iterierbares Objekt von Permutationen erzeugen. Ein solches Objekt ist in den folgenden Beispielen ps vom Typ Permiter.
let ps = Permiter([1, 2, 3, 5, 7])
println(ps.v)
for p in ps
println(p)
end
end
[1, 2, 3, 5, 7]
[1, 2, 5, 3, 7]
[1, 5, 2, 3, 7]
[5, 1, 2, 3, 7]
[5, 1, 2, 7, 3]
[1, 5, 2, 7, 3]
[1, 2, 5, 7, 3]
[1, 2, 7, 5, 3]
[1, 2, 7, 3, 5]
[1, 7, 2, 3, 5]
[1, 7, 2, 5, 3]
⋮
[5, 2, 1, 3, 7]
[2, 5, 1, 3, 7]
[2, 1, 5, 3, 7]
[2, 1, 3, 5, 7]
[2, 1, 3, 7, 5]
[1, 2, 3, 7, 5]
Objekte vom Typ Permiter sind flexibel einsetzbar.
let ps = Pm.Permiter([:A, "eins", 7.5, 4])
println(ps.v)
for p in ps
println(p)
end
end
Any[:A, "eins", 7.5, 4]
Any[:A, 7.5, "eins", 4]
Any[7.5, :A, "eins", 4]
Any[7.5, :A, 4, "eins"]
Any[:A, 7.5, 4, "eins"]
Any[:A, 4, 7.5, "eins"]
Any[:A, 4, "eins", 7.5]
Any[4, :A, "eins", 7.5]
Any[4, :A, 7.5, "eins"]
⋮
Any[7.5, "eins", 4, :A]
Any[7.5, "eins", :A, 4]
Any["eins", 7.5, :A, 4]
Any["eins", :A, 7.5, 4]
Any["eins", :A, 4, 7.5]
Any[:A, "eins", 4, 7.5]
Julia Version: 1.0.1