debianforum.de

Ihr habt es sicher längst erraten: Anagramme und/oder Permutation wird benötigt, wenn die Anordnung der Werte für die Rechenschlange durch systematischen Austausch ermittelt werden soll, um wirklich alle Ergebnisse zu "erwischen". [vergl. Beitrag gestern]

Ich dachte mir: Das wird einfach, da gibt's viele Vorlagen, und fand auch gleich eine in der Wikipedia [1]; auf das Bequemste in Pseudocode vorformuliert. Ein echtes Kinderspiel, und die Erklärung ist auch dabei. Dachte ich. Allerdings: es funktioniert nicht. Hier gibt es meine Transkribtion in lauffähiges Pascal, als Kommentar den Wiki-Pseudocode und den fehlerhaften Output gleich angefügt. Die Schlange habe ich erst gar nicht damit gefüttert!

reschl_nach_wiki.pas
42274

Wer ist hier der Dumme ist: Wikipedia oder ich? Komisch ist auch, dass der rekursive Aufruf gleich an zwei mal stattfindet. Alte Programmiererweisheit: Rekursiv geht meistens schief.

Nun denn, weiter nach einer netten Vorlage gesucht und diese hier gefunden: Permutation in verschiedenen Programmiersprachen: [2] Das C-Programm sah gut aus, und nachdem wir gerade im Forum eine aktuelle C-Ecke haben, wollte ich das probieren. Nachdem ich die Fehlermeldungen des gcc wegbekommen hatte, lief es auch korrekt.

permu.c
42275

Nebenbei: Es hat mir auch gefallen, wie pfiffig hier die "sizeof" des Arrays ermittelt wird - unabhängig von der Größe des einzelnen Elements und ihrer Anzahl. Unübersichtlich finde ich hingegen, dass dieses Array-Größe "n" dann durch alle Funktionen hindurchgeschleift wird. Für mich wäre das ein klarer Fall für eine globale Variable.

Der nächste Schritt war, das C-Programm nach Pascal zu übertragen um zu testen, ob auch dieses korrekt läuft. Tut es:

reschl_perm.pas
42276

Und nun – endlich! – wird die Rechenschlange damit gefüttert:

reschl_perm_0.pas
42277

Anmerkungen:
1) Wie in C lassen sich auch in Freepascal Variablen mit Anfangswerten initialisieren, wie hier das Array.
2) Die Procedure swap bekommt "Var"-Parameter und liefert somit ihr Tausch-Ergebnis zurück.
3) Wenn die neue Permutation fertig ist, wird sie in "Ergebnis" getestet und bei Gleichheit angezeigt, damit könnte das Programm auch anhalten *) und braucht nicht mehr alle weiteren Permutationen zu ermitteln. Da ich aber schon weiß, dass ich’s später noch brauche, lasse ich es fertig permutieren.
4) Die Problematik des Gleichheitstests bei Real-Werten hatte ich schon erwähnt. Aber es funktioniert korrekt.

*) Der richtige Weg zum Beenden wäre allerdings, aus der aktuellen Rekursion stufenweise zurückzuspringen, was weiteren Code erfordert ("Flag" setzten und abfragen, Rekursionszähler oder ähnliches)

So, nun kommt das letzte Programm dieser Reihe. Wir wollen wissen, wieviele (ganzzahlige) Ergebnisse sich insgesamt mit den Vorgabezahlen erzielen lassen. Außerdem soll auch gleich die Frage geklärt werden, ob bestimmte Ergebnisse sich mit unterschiedlich aufgemischen Arrays erreichen lassen. Wie schon vorher bei den Random-Programmen wird das mit zwei Durchlaufzählern erreicht. Der Output spricht, denke ich, für sich. Probiert es aus!

reschl_perm_1.pas
42278

Nun war von der Anna, dem Anagramm, noch gar nicht die Rede. Aber wir wissen ja, dass ein Anagramm und eine Permutation das selbe ist. (Beim A. meist nur nach gültigen Wörtern gefiltert, siehe an aus dem Debian-Repo) Für das Anagramm habe ich ein besonders feines Programm in [3] gefunden. Hier ersetzen die intern und automatisch mitgeführten Längen-Schlüssel der Pascal-Strings einen Teil der Jongliererei mit den Tausch-Indeces, und es entsteht ein ein sehr kurzes, elegantes Programm. Da sich ja nun auch die einzelnen Bytes eines Strings als numerische Werte gebrauchen lassen und der Wertebereich für unser Aufgabe völlig ausreicht, kann es ohne weiteres dafür eingesetzt werden. Lediglich müssen in Pascal die "Char"s des Strings explizit zu "Byte"s re-typed werden (Type-Cast). Das aber nur bei der Berechnung des Ergebnisses. Hier das Prog:

reschl_ana.pas
42279

Korrektur/Ergänzugn: Ein paar Zeichen im NoPaste sind mir entschwunden. Der Aufruf im Hauptprogramm lautet: Wer nun dieses Türchen weit genug aufgemacht hat, findet auch hier am Schluss in kleines Film-Schmankerl auf meiner HP, per Simplescreerecorder erstellt:

https://www.jodre.de/df_adv_kal_19.12.24/

Speziell für unsere KI-Tester hier: Wäre es nicht mal ganz nett, den Aufgabetext einer KI vorzuwerfen und diese
a) um eine Lösung und
b) um ein Programm, welches das Problem löst, zu bitten?

Freundliche Advents-Grüße vom TuxPeter!

[1] https://de.wikipedia.org/wiki/Heap-Algorithmus

[2] https://www.geeksforgeeks.org/heaps-alg ... mutations/

[3] https://www.bastisoft.de/programmierung ... siker.html

Ach, das ist ein Doppeltuerchen! Ich habe mich schon gefragt, warum du das Permutieren gestern so hinter dem Berg gehalten hast.

MIr war das Durchdenken der Algorithmus dann doch zu hoch, also habe ich nur den rekursiven Heap-Algorithmus aus der Wikipedia in C umgesetzt: Ich verwende einfach argv als Array. Bequem ist, dass ich dann die Laenge nicht fuer die Ausgabe durchschleifen muss, weil argv NULL-terminiert ist.

swap() musste ich implementieren. Deine Version war nicht in C sondern in C++, wo es eine Template-Funktion swap() gibt.

Hi, danke für den Beitrag, jedenfalls funktioniert Deine Version der Umsetzung prima. So ganz kapiert habe ich aber nicht, wie die Params beim Programmaufruf übernommen werden werden, wie also das Hauptprogr. funktioniert

Ich werde das nachher mal in Pascal nachbauen und schauen, was ich beim ersten Versuch anders gemacht habe - vermutlich die begin / end - Klammerung.

Übrigens habe ich mal kurz die "Abwärtskompatibilität" des Pascal-Programmes mit den Strings getestet, in der Dosbox (die ich immer mit an Bord habe) unter TP5. Geht auch. Die anderen Pascal-Progs müssten umgebaut werden, da TP5 nur einfache Datentypen als Funktionsergebnis kennt - im Gegensatz zu FreePascal. Also kein Array als Funktionstyp möglich. Außerdem müssten alle Kommentare mit // usw ... in {} eingefasst werden.

TuxPeter hat geschrieben:

18.12.2024 22:59:47

https://www.jodre.de/df_adv_kal_19.12.24/

Zu deiner Frage, warum bei den Anagrammen von ``LEBEN'' zweimal ``NEBEL'' vorkommt: Das ist einfach, das zweite Nebel ist wie das erste nur die beiden `E' sind vertauscht.

Bei der Permutation werden stupide Positionen getauscht, unabhaengig von ihrem Inhalt. Dass zwei Positionen zufaellig den gleichen Inhalt haben und somit am Ende nicht mehr unterscheidbar sind, ist dem Algorithmus egal. Falls man doppelte Werte hat, muss man am Ende die Ergebnisliste von um die doppelten Ergebnisse bereinigen.

Einfaches Extrembeispiel: Wieviel Permutationen gibt es von ``a a a''? Das Programm generiert 6 identische Zeilen.

TuxPeter hat geschrieben:

18.12.2024 22:59:47

Ich dachte mir: Das wird einfach, da gibt's viele Vorlagen, und fand auch gleich eine in der Wikipedia [1]; auf das Bequemste in Pseudocode vorformuliert. Ein echtes Kinderspiel, und die Erklärung ist auch dabei. Dachte ich. Allerdings: es funktioniert nicht. Hier gibt es meine Transkribtion in lauffähiges Pascal, als Kommentar den Wiki-Pseudocode und den fehlerhaften Output gleich angefügt. Die Schlange habe ich erst gar nicht damit gefüttert!

reschl_nach_wiki.pas
42274

Wer ist hier der Dumme ist: Wikipedia oder ich? Komisch ist auch, dass der rekursive Aufruf gleich an zwei mal stattfindet. Alte Programmiererweisheit: Rekursiv geht meistens schief.

Hier bin ich immer noch am raetseln. Das wird dadurch erschwert, dass ich Pascal kaum kenne. Mit der Rekursion an sich hat es nichts zu tun. Der Grund fuer die beiden Rekursionen ist in der Wikipedia-Seite auch erklaert: Damit spart man sich unnoetige Vergleiche.

Meiner Vermutung nach wird das Problem in der Parameteruebergabe als entweder Call-by-Value oder Call-by-Reference liegen. Wann wird denn in Pascal was verwendet? Wie kann man das unterscheiden bzw. gezielt waehlen? Wenn das gleich wie in der C-Implementierung ist, sollte es auch gleich funktionieren. Fuer mich sieht es derzeit aus, wie wenn alle Parameter gleich uebergeben werden. Aber das ist nur eine erste Vermutung.

Ich will mir das gerne noch genauer anschauen ...

Meillo hat geschrieben:

22.12.2024 19:56:29

Meiner Vermutung nach wird das Problem in der Parameteruebergabe als entweder Call-by-Value oder Call-by-Reference liegen. Wann wird denn in Pascal was verwendet?

Pascal verwendet normalerweise Call-by-Value. Funktionsparamter, die per Referenz übergeben werden sollen, müssen mit "var" deklariert werden.

MSfree hat geschrieben:

22.12.2024 20:05:52

Meillo hat geschrieben:

22.12.2024 19:56:29

Meiner Vermutung nach wird das Problem in der Parameteruebergabe als entweder Call-by-Value oder Call-by-Reference liegen. Wann wird denn in Pascal was verwendet?

Pascal verwendet normalerweise Call-by-Value. Funktionsparamter, die per Referenz übergeben werden sollen, müssen mit "var" deklariert werden.

Danke fuer den Hinweis.

Bei swap() wird `var' verwendet, wie das auch noetig ist.

Dann muss vielleicht nur bei generate() der zweite Parameter `A' als `var' uebergeben werden, so dass das Array nicht kopiert, sondern jeweils nur veraendert wird. Das unterscheidet jedenfalls die Pascal- von der C-Implementierung.

Habe soeben noch mal kurz getestet und das Programm ('Rechenschlange nach Wiki') mit einem Var-Param ausgestattet, also lautet der Prozedur-Kopf somit:
Ergebnis: Immer noch falsch, allerdings andere Fehler. Das alte Ergebnis, mit Werte-Parameter, also ohne Var ... Ich habe z.Zt. nicht den Nerv, aus dem Versuch ein funktionsfähiges Programm zu machen, zumal es ja genug funktionierende Versionen gibt. Vermute aber nach wie vor, dass die begin-end-Klammerung der Anweisungen an irgend einer Stelle falsch ist. (Nachdem Meillos C-Umsetzung eine richtige Interpretation des Pseudocodes geliefert hat) Vermutlich wäre mein Weg, diese C-Version in Pascal zu transkribieren und dann weiter zu schauen. Es war ja auch schon aufgrund der for ... loop im Wiki klar, dass der Wikipedia-Autor von einem C-Programm ausgegangen ist

Was es mit dem Anagramm vom "LEBEN" auf sich hat, war mir schon klar, es war als kleines Rätsel am Rande gedacht - und das ist ja jetzt gelöst. Als ich das getestet hatte, war mir das Anagramm Nebel - Leben schon vorher im Kopf gewesen, und ich war etwas verblüfft, bis ich die Anzahl der Ergebnisse geprüft hatte und mir klar wurde, dass es das "andere E" war.

Es freut mich jedenfalls sehr, dass meine Spielereien einiges Echo ausgelöst haben!

Hier ist der zweite Fehler: Der Pseudocode lautet: `k-1' darf nicht mehr iteriert werden. Du musst deine Schleife abaendern in: Dann wird die Ausgabe stimmen.

Es werden durch diese Aenderung nur uebermaessige Zeilen entfernt.


Die var-Aenderung war auch noetig, weil du sonst z.B. die Kombination 021 nicht bekommst.

Recht hast Du.
Hatte natürlich in der funktionierenden 2. Version gleich ein Var-Param für das Array verwendet - quasi automatisch, schon weil das Ergebnis ja aus der Procedur auch wieder heraus muss ... nur dann in der ersten nicht ... und die for-Loop ist mit der Abfrage auf i < k-1 eigentlich auch recht eindeutig. Typischer Fall von an der falschen Stelle herumprobiert.

Wenn man nicht vorhat die Dimension des Array-Typs innerhalb der Prozedur/Funktion zu verändern, dann sollte man den Parameter besser einschränkend mit `const' anstelle `var' in der Kopfzeile deklarieren. Setlength z.B. funktioniert dann in der Routine nicht mehr, Änderungen an einzelnen Elementen aber weiterhin. Das const/var bezieht sich somit auf den Array-Zeiger und nicht auf den Array-Inhalt.

tobo hat geschrieben:

23.12.2024 00:51:58

... den Parameter besser einschränkend mit `const' anstelle `var' in der Kopfzeile deklarieren. ...
Änderungen an einzelnen Elementen [funktionieren] aber weiterhin

Die Inhalte müssen aber geändert werden. Der Compiler meint dann beim Aufruf der Swap-Procedur: Oder verstehe ich Dich falsch, vielleicht meinst Du eine explizite Übergabe als Pointer?

TuxPeter hat geschrieben:

23.12.2024 09:10:09

tobo hat geschrieben:

23.12.2024 00:51:58

... den Parameter besser einschränkend mit `const' anstelle `var' in der Kopfzeile deklarieren. ...
Änderungen an einzelnen Elementen [funktionieren] aber weiterhin

Die Inhalte müssen aber geändert werden. Der Compiler meint dann beim Aufruf der Swap-Procedur:

Code: Alles auswählen

reschl_perm.pas(40,22) Error: Can't assign values to const variable

Oder verstehe ich Dich falsch, vielleicht meinst Du eine explizite Übergabe als Pointer?

Ich habe ja auch explizit von einem Array-Typen geschrieben, du schreibst von der Swap-Prozedur, also von 2 Integer - das sind speichertechnisch 2 grundverschiedene Fälle!

Dynamische Arrays (oder z.B. auch Ansistrings) sind Referenztypen, deren Übergabe als Referenz (Adresse, by reference) erfolgt. Wenn du z.B. ein dynamisches Array einer anderen Variablen zuweist, dann weist du nur die Adresse auf das Array zu, was günstig ist, da deshalb nicht der gesamte Inhalt kopiert werden muss. Bezogen auf das Argument ist bei einem const-Parameter also die Referenz schreibgeschützt, nicht die Daten. Bei einem var-Parameter kann man aber diese Referenz per z.B. neuem setlength oder Zuweisen von nil verändern. Ohne Modifikator wird die Referenz als Wert übergeben und somit bleiben jedwede Änderungen daran lokal.

Ein Intgeger ist ein einfacher Typ, der per Wert (by Value) übergeben wird, also eine Kopie seiner Daten. Das betrifft den Fall, das weder var noch const angeben ist. Änderungen am Inhalt verbleiben damit in der Routine und können nicht zurückgegeben werden. Mit var wird er als Referenz übergeben, was sämtliche Änderungen weiterreicht. Mit const wird er jedoch im Unterschied dazu - Default-Einstellungen beim Kompilieren vorausgesetzt - wieder als (schreibgeschützter) Wert übergeben, was dann auch die Fehlermeldung auslöst.