Adventskalender 19. Dezember 2024 - Permutation und Anagramm

[TuxPeter]

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:

Code: Alles auswählen

begin
Perm ('', #1#2#3#6#10#11#13); 
end.

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

[Meillo]

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:

Code: Alles auswählen

/*
** Generate permutations with Heap algorithm
** based on https://de.wikipedia.org/wiki/Heap-Algorithmus
*/
#include <stdio.h>

void
output(char *A[])
{
        char **cp=A;

        while (*cp) {
                if (cp != A) {
                        putchar(' ');
                }
                printf("%s", *cp++);
        }
        putchar('\n');
}

void
swap(char **a, char **b)
{
        char *temp=*a;
        *a = *b;
        *b = temp;
}

// der anfaengliche Aufruf von generate geschieht mit k == length(A)
void
generate(int k, char *A[])
{
        int i=0;

        if (k == 0) {
                return;
        }

        if (k == 1) {
                output(A);
                return;
        }

        // erzeuge Permutationen mit unveraendertem kten Element
        generate(k - 1, A);

        // erzeuge Permutationen mit dem kten Element vertauscht mit jedem (k-1)sten Element
        // alle Array-Zugriffe sind 0-basiert, d.h. das kte Element ist bei [k-1]
        for (i=0; i < k-1; i++) {
                // vertausche 2 Elemente in Abhaengigkeit von der Parität von k (gerade oder ungerade)
                if (k % 2 == 0) {
                        swap(&A[i], &A[k-1]);
                } else {
                        swap(&A[0], &A[k-1]);
                }
                generate(k - 1, A);

        }
}

int
main(int argc, char *argv[])
{
        generate(argc-1, argv+1);
        return 0;
}

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.

[TuxPeter]

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.