Permutationen

8 Minuten zum Lesen

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.

Anordnungen von drei 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

Startseite