Permutationen nicht rekursiv berechnen

[Helmut Weber]

Hallo liebe Schlaumeier, :-)

was respektvoll und gar nicht abwertend gemeint ist,

ich suche nach einem Weg,
Permutationen ohne Rekursion zu berechnen,
also z.b. die 24 Möglichkeiten, "a", "b", "c" und "d" anzuordnen.

Warum? Einfach so, weil ich es wissen will,
und weil Rekursionen ja, soviel ich davon verstehe,
den Speicher auffressen. Praktisch wohl kein Problem,
aber theoretisch sollte es doch ohne Rekursion gehen, oder nicht?

Googlen kann ich schon.
"permutation algorithm" ergibt 94000 Treffer.

Wenn ich hier keine Antwort kriege,
lese ich sie alle, und melde mich dann in etwa 300 Jahren wieder. ;-)

[Marcus O. M. Grabe]

On Sun, 01 Jan 2006 01:06:31 +0100, Helmut Weber

Post by Helmut Weber
Hallo liebe Schlaumeier, :-)
was respektvoll und gar nicht abwertend gemeint ist,
ich suche nach einem Weg,
Permutationen ohne Rekursion zu berechnen,
also z.b. die 24 Möglichkeiten, "a", "b", "c" und "d" anzuordnen.
Warum? Einfach so, weil ich es wissen will,
und weil Rekursionen ja, soviel ich davon verstehe,
den Speicher auffressen. Praktisch wohl kein Problem,
aber theoretisch sollte es doch ohne Rekursion gehen, oder nicht?
Googlen kann ich schon.
"permutation algorithm" ergibt 94000 Treffer.
Wenn ich hier keine Antwort kriege,
lese ich sie alle, und melde mich dann in etwa 300 Jahren wieder. ;-)

Hi,

ich nehme mal Deine Frage ernst, obwohl sie mich irgendwie nach
Sylvester-Scherz anhört.

Du möchtest doch einfach die Fakultät berechnen.

Function Fac2(ByVal varParam1 As Variant) As Variant

Dim varTemp As Variant
Dim varI As Variant


varTemp = 1

For varI = 1 To varParam1
varTemp = varTemp * varI
Next varI

Fac2 = varTemp

End Function

Marcus [gerade noch übrig aus 2005]

[Helmut Weber]

Hallo Marcus

Post by Marcus O. M. Grabe
ich nehme mal Deine Frage ernst, obwohl sie mich irgendwie nach
Sylvester-Scherz anhört.
Du möchtest doch einfach die Fakultät berechnen.

Nein, ich möchte alle Permutationen erzeugen.
Ich habe im Net nur Algorithmen gefunden,
die auf Rekursion basieren,
und schaffe es nicht ohne Rekursion.

Helmut Weber

[Herfried K. Wagner [MVP]]

Hallo Helmut!

Post by Helmut Weber
was respektvoll und gar nicht abwertend gemeint ist,
ich suche nach einem Weg,
Permutationen ohne Rekursion zu berechnen,
also z.b. die 24 Möglichkeiten, "a", "b", "c" und "d" anzuordnen.
Warum? Einfach so, weil ich es wissen will,
und weil Rekursionen ja, soviel ich davon verstehe,
den Speicher auffressen. Praktisch wohl kein Problem,
aber theoretisch sollte es doch ohne Rekursion gehen, oder nicht?

Jede Rekursion lässt sich in ein iteratives Verfahren überführen. Am
Einfachsten geht dies mit einem Stapel (Stack).

Hier ein iteratives (von mir unbesehenes) Verfahren (schnell implementiert
nach der Vorlage auf
<URL:http://www.geocities.com/permute_it/01example.html>):

\\\
Private Sub Form_Load()
Dim s(0 To 3) As String
s(0) = "a"
s(1) = "b"
s(2) = "c"
s(3) = "d"
Dim Results As Collection
Set Results = New Collection
Call Permute(s, Results)
Debug.Print Results.Count
Dim x As Variant
For Each x In Results
Debug.Print x
Next x
End Sub

Private Sub Permute( _
ByRef Items() As String, _
ByVal Results As Collection _
)
Dim n As Long
n = UBound(Items) + 1
ReDim p(0 To n) As Integer
Dim i As Long
For i = 0 To n
p(i) = i
Next i
Call AddPermutation(Items, Results)
i = 1
While i < n
p(i) = p(i) - 1
If (i Mod 2) <> 0 Then
j = p(i)
Else
j = 0
End If
Call Swap(Items(j), Items(i))
Call AddPermutation(Items, Results)
i = 1
While (p(i) = 0)
p(i) = i
i = i + 1
Wend
Wend
End Sub

Private Sub AddPermutation( _
ByRef Permutation() As String, _
ByVal Results As Collection _
)
Dim s As String
Dim i As Long
For i = 0 To UBound(Permutation)
s = s & Permutation(i)
Next i
Call Results.Add(s)
End Sub

Private Sub Swap(ByRef i1 As String, ByRef i2 As String)
Dim t As String
t = i1
i1 = i2
i2 = t
End Sub
///

[Helmut Weber]

Hallo Herfried,

funktionieren tut's schon mal.

und für den Rest der Woche
hab ich jetzt was zum Nachdenken.

Danke

Helmut Weber

[Thorsten Albers]

Post by Helmut Weber
und weil Rekursionen ja, soviel ich davon verstehe,
den Speicher auffressen.

Es sind lediglich die (Prozedur-)lokalen Variablen, die den Speicher dabei
'auffressen'. Wenn Du diese weitestgehend vermeidest oder reduzierst, gibt
es keine Probleme mit Rekursionen.

[Andreas Born]

Hallo Thorsten,

Post by Thorsten Albers
Es sind lediglich die (Prozedur-)lokalen Variablen, die den Speicher
dabei 'auffressen'. Wenn Du diese weitestgehend vermeidest oder
reduzierst, gibt es keine Probleme mit Rekursionen.

Dennoch wäre ich damit vorsichtig, wenn die Rekursionstiefe sehr groß
werden kann.

Es wird schließlich für jede "Rekursionsebene" zusätzlicher Platz auf
dem stack benötigt, und dieser ist im allgemeinen begrenzt. Ein Stack
Overflow Fehler ist da noch das beste was einem passieren kann.

Ich würde Rekursionen ausschließlich dann verwenden, wenn ich die
maximale Rekursionstiefe kenne und sicher weiß, daß der Stack ausreicht.

Allerdings ist es recht einfach, jede beliebige Rekursion in eine
Iteration mit eigenem Stack umzuwandeln, was zudem auch noch
performanter ist. Auch kann man dann soviele prozedurlokale Variablen
verwenden, wie man will, weil es dann keine Rolle mehr spielt.

Viele Grüße und
ein schönes neues Jahr,
Andreas

[Thorsten Albers]

Post by Andreas Born
Dennoch wäre ich damit vorsichtig, wenn die Rekursionstiefe sehr groß
werden kann.
Es wird schließlich für jede "Rekursionsebene" zusätzlicher Platz auf
dem stack benötigt, und dieser ist im allgemeinen begrenzt. Ein Stack
Overflow Fehler ist da noch das beste was einem passieren kann.
Ich würde Rekursionen ausschließlich dann verwenden, wenn ich die
maximale Rekursionstiefe kenne und sicher weiß, daß der Stack ausreicht.
Allerdings ist es recht einfach, jede beliebige Rekursion in eine
Iteration mit eigenem Stack umzuwandeln, was zudem auch noch
performanter ist. Auch kann man dann soviele prozedurlokale Variablen
verwenden, wie man will, weil es dann keine Rolle mehr spielt.

Klar, irgendwann ist jeder limitierte Speicher voll. Aber das gilt für jede
Art der Realisierung eines wiederholt ausgeführten Vorganges.

Nebenbei sollte man vielleicht auch noch erwähnen, daß Rekursionen deswegen
nach Möglichkeit vermieden werden sollten, weil sie den Code schlechter
lesbar und nachvollziehbar machen, zumindest, wenn sie in größerem Maßstab
angewendet werden.

[Peter Fleischer]

Thorsten Albers wrote:
...

Post by Thorsten Albers
Nebenbei sollte man vielleicht auch noch erwähnen, daß Rekursionen
deswegen nach Möglichkeit vermieden werden sollten, weil sie den Code
schlechter lesbar und nachvollziehbar machen, zumindest, wenn sie in
größerem Maßstab angewendet werden.

...

Thorsten,
ohne konkrete Randbedingungen muss ich dieser allgemeinen Aussage
widersprechen. Für mich ist ein rekursiv gestalteter Code in bestimmten
Anwendungsfälle viel lesbarer und auch einfacher, egal, ob Rekursionstiefe
feststeht oder nicht.

Peter

[Herfried K. Wagner [MVP]]

Hallo Peter!

Post by Peter Fleischer

Post by Thorsten Albers
Nebenbei sollte man vielleicht auch noch erwähnen, daß Rekursionen
deswegen nach Möglichkeit vermieden werden sollten, weil sie den Code
schlechter lesbar und nachvollziehbar machen, zumindest, wenn sie in
größerem Maßstab angewendet werden.

...
ohne konkrete Randbedingungen muss ich dieser allgemeinen Aussage
widersprechen. Für mich ist ein rekursiv gestalteter Code in bestimmten
Anwendungsfälle viel lesbarer und auch einfacher, egal, ob Rekursionstiefe
feststeht oder nicht.

Dem stimme ich zu. Nicht zuletzt wird eine rekursive Implementierung oft
gewählt, um zu partitionieren und das Problem in kleinere Teilprobleme
aufzubrechen, die dann leicht lösbar und verständlich sind.

[Andreas Born]

Hallo Herfried,

Post by Herfried K. Wagner [MVP]

Post by Peter Fleischer
Für mich ist ein rekursiv gestalteter Code in
bestimmten Anwendungsfälle viel lesbarer und auch einfacher,
egal, ob Rekursionstiefe feststeht oder nicht.

Dem stimme ich zu. Nicht zuletzt wird eine rekursive Implementierung
oft gewählt, um zu partitionieren und das Problem in kleinere
Teilprobleme aufzubrechen, die dann leicht lösbar und verständlich
sind.

Das sehe ich anders, allerdings in einem anderen Kontext.

Bestimmte Algorithmen lassen sich am einfachsten als Rekursion
implementieren, und bleiben dabei übersichtlicher als die entsprechenden
"iterativen" Verfahren. Ich denke in diesem Punkt stimmen wir überein.

Wenn es um die Begriffe "iterativ" und "rekursiv" geht, werden jedoch
häufig Fehler gemacht, da nie hinterfragt wird, ob man diese Begriffe
nun auf den Algorithmus oder die Implementierung desselben bezieht.

Meist wird der Begriff "rekursiv" benutzt, wenn sich eine Funktion
selbst aufruft. Das ist der technische Aspekt. Es ist aber weder
notwendig noch hinreichend, um daraus den hinter dieser Funktion
stehenden Algorithmus als "rekursiv" bezeichnen zu müssen oder zu
können.

Genauer gesagt:
Jeder rekursiv aufgebaute Algorithmus kann auch iterativ implementiert
werden, und umgekehrt, d.h. ohne den Algorithmus selbst zu verändern.

Und um den Bezug zu meinem "Einspruch" wiederherzustellen:
Man kann jeden rekursiven Algorithmus iterativ implementieren, ohne auf
die von Dir genannten Vorteile verzichten zu müssen. Der Nachteil ist,
daß man einen eigenen Stack verwenden muß, der Vorteil, daß man nicht
mit der Stack-Größe zu kämpfen hat, daß man Fehler trotz Optimierungen
vernünftig verarbeiten kann.

Wenn man die maximale Rekursionsteife nicht kennt oder nicht bestimmen
kann, sollte man dennoch entweder auf einen wirklich iterativen
Algorithmus zurückgreifen, oder eine Überprüfung der Rekursiosnstiefen
vornehmen, egal wie die Implementierung nun aussieht. Tut man das nicht,
sind solche (un)schönen Sachen wie buffer overflow exploits machbar;
ähnliches haben wir ja mit der Sicherheitslücke bei der JPEG-KOmpression
schon gehabt.

Die Gretchenfrage: wenn man die Rekursionstiefe nicht kennt, und
die Größe des Stacks ebenfalls nicht, der code aber auf Speed optimiert
werden soll, wie verhindert man stack overflows? (bei OS < XP SP2 oder
Windows Vista)

Mein Fazit: Rekursive Funktionsaufrufe sind ausschließlich in
Situationen vertretbar, bei denen die Rekursionstiefe durch den
Algorithmus begrenzt ist, und der Stack nicht aufgebraucht wird. Die
meisten rekursiven Algorithmen haben jedoch genau den Nachteil, daß
diese Begrenzung vom INPUT abhängig ist, und die max Rekursiontiefe
nicht direkt berechnet werden kann.

Man kann all diesen Problemen aus dem Weg gehen, wenn man diese
Algorithmen iterativ implementiert.


Viele Grüße,
Andreas

[Andreas Born]

Post by Thorsten Albers

Post by Andreas Born
Dennoch wäre ich damit vorsichtig, wenn die Rekursionstiefe sehr groß
werden kann.
Es wird schließlich für jede "Rekursionsebene" zusätzlicher Platz auf
dem stack benötigt, und dieser ist im allgemeinen begrenzt. Ein Stack
Overflow Fehler ist da noch das beste was einem passieren kann.

Klar, irgendwann ist jeder limitierte Speicher voll. Aber das gilt
für jede Art der Realisierung eines wiederholt ausgeführten Vorganges.

Klar. Aber es ist doch ein Unterschied, ob die Grenze bei wenigen KB
liegt, oder im extremfall bei der Größe des RAM oder gar der Festplatte.
Ich finde das sollte man nicht gleichsetzen, zumal eine vernünftige
Fehlerbehandlung bei optimierten Rekursionen nicht immer möglich ist.

Post by Thorsten Albers
Nebenbei sollte man vielleicht auch noch erwähnen, daß Rekursionen
deswegen nach Möglichkeit vermieden werden sollten, weil sie den Code
schlechter lesbar und nachvollziehbar machen, zumindest, wenn sie in
größerem Maßstab angewendet werden.

Ack, sofern die Rekursionen eigene oder wenig bekannte Algorithmen
darstellen, dann sehe ich das genauso. Wenn es sich aber um
(standard-)Algorithmen handelt, halte ich diese für durchaus lesbar und
praktikabel, da dies in aller Regel auch die kompakteste Implementierung
ist.

Viele Grüße,
Andreas

[Michaela Meier]

Post by Helmut Weber
ich suche nach einem Weg,
Permutationen ohne Rekursion zu berechnen,
also z.b. die 24 Möglichkeiten, "a", "b", "c" und "d" anzuordnen.

Hallo,
Eigentlich muß man sich dafür nur genau anschauen wie man es selbst per
Hand auf einen Zettel schreiben würde.
Laß dies mal durchlaufen und schaue dir an wie die Kombinationen
aufgebaut werden.
HTH
Michaela

zeichen = "abcde"
zmax = Len(zeichen)
pmax = 1
For i = 2 To zmax
pmax = pmax * i
Next
Dim permutation() As String
ReDim permutation(pmax)
p = pmax
For z = 1 To zmax
zz = zmax - z + 1
k = 0
p = p / zz
For jj = 1 To pmax / (p * zz)

bb = 0

For b = 1 To zmax - z + 1
Do
bb = bb Mod zmax + 1
n = Mid(zeichen, bb, 1)
Loop Until InStr(permutation(k + 1), n) = 0
For j = 1 To p
k = k + 1
permutation(k) = permutation(k) & n
Debug.Print k, permutation(k)
Next
Next
Next
Next

[Helmut Weber]

Herzlichen Dank,

es gibt viel zu denken.

Helmut Weber