Permutationen und Algorithmus

Re(8): Permutationen und Algorithmus

JosefJobbaggy — Fri, 27 Jun 2003 09:36:00 GMT

Tja, das finde ich aber merkwürdig. Der Code spuckt mir folgendes Ergebnis aus:
Eingabe abc
Ausgabe 3xa, 3xb, 3xc, 2x perm(ab), 2x perm (ac), 2xperm(bc), perm(abc)

Ich habs auch mit anderen Strings ausprobiert, und bin zu dem Schluß gekommen, daß mein Code einfach zu oft iteriert, da immer das gleiche Muster herauskommt:
Wenn l=Länge des Strings, dann kommt immer lx(1Buchstabe), (l-1)x(2Buchst.) usw.
Ich schätze, die Rekursion wiederholt die Schleife zu oft, aber mit etwas anderem habe ich es bis jetzt noch nicht hingekriegt.

Josef

Re(7): Permutationen und Algorithmus

Dennis666 — Fri, 27 Jun 2003 04:22:50 GMT

Also ich würde auch mal gerne wissen wie du auf doppelte Permutationen kommst ?
Habe es nachgerechnet bei mir kommen keine doppelten Ergebnisse heraus !
MFG,
Dennis

Re(5): Permutationen und Algorithmus

JosefJobbaggy — Thu, 26 Jun 2003 18:20:05 GMT

Ja, daran habe ich auch schon gedacht. Doch so wie ich das umsetzen könnte, ist das nicht unbedingt schnell. Da kommt man mit einem String von 10 Buchstaben schnell mal auf 4,5 Mio Permutationen....
Ich dachte, daß es vielleicht einen eleganteren Lösungsweg gäbe, der mir erst gar keine Duplikate erzeugt.

Trotzdem danke für den Vorschlag. Wenns nicht anders geht, werd ichs wohl so machen müssen.

Josef

Re(4): Permutationen und Algorithmus

maschwa — Thu, 26 Jun 2003 14:26:10 GMT

Ich hätte folgenden spontanen vorschlag:

"duplikate sollen ausgeschlossen werden", da bieten sich für mich dictionaries aller art an. Pack einfach deine resultate in ein dictionary (zb hashtable, sortedlist,...), dadurch werden duplikate vermieden. Danach iterierst du über das dictionary.

Ist wie gesagt nur ein spontaner vorschlag, aber vielleicht hilft er dir

Re(3): Permutationen und Algorithmus

TheTrumpeter — Thu, 26 Jun 2003 10:15:37 GMT

Jaja, ich sagte ja, man erkennt's am Beispiel...

Re(2): Permutationen und Algorithmus

JosefJobbaggy — Thu, 26 Jun 2003 10:03:41 GMT

Naja, dachte, das ist eigentlich egal. Einerseits sieht man am Beispiel eh, daß es in VC++ ist, andrerseits gehts mit nur um den Algorithmus. Da ists egal, welche Sprache das ist

Josef

Re: Permutationen und Algorithmus

TheTrumpeter — Thu, 26 Jun 2003 09:58:02 GMT

Vielleicht hättest Du noch dazusagen sollen, in welcher Sprache das Programm sein soll, obwohl's aus Deinem Beispielprogramm eh relativ eindeutig ersichtlich ist...

Permutationen und Algorithmus

JosefJobbaggy — Thu, 26 Jun 2003 09:55:02 GMT

Hi!

Eine Frage an die AlgoDat-Spezialisten unter Euch.
Ich soll ein Programm schreiben, das mir für einen gegebenen String alle Permutationen sowie für alle Unterstrings (das sind diejenigen Strings, die man erhält, wenn man vom Originalstring ein oder mehrere Chars entfernt) erhält.
Kleines Beispiel: String abc
Ausgabe: a, b, c, perm (ab), perm (ac), perm (bc), perm (abc).
Wobei "perm (xy)" die möglichen Permutationen von xy sind.

Nun gut, die Permutationen sind kein Problem, die habe ich. Allerdings gerate ich bei den Unterstrings in arge Schwierigkeiten. Ich habe es zwar geschafft, alle möglichen anzeigen zu lassen, jedoch erhalte ich da viele Möglichkeiten mehrmals, und das darf auch nicht sein.

Ok, nun meine Frage: Kennt jemand einen Algorithmus, der die Aufgabenstellung besser löst als meiner?

Josef

Hier noch ein kurzer Code-Auszug aus meinem Programm:

void CStringPermutationsDlg::permute_all (CString str, int l)
{
if (l==0)
   Sleep (0);
else
  {
    for (int o=1; o<l+1; o++)
   {
       permute (str.Right(o), str.Right(o).GetLength());
       rotate_String (str.GetLength(), str);
       permute_all (str, l-1);
                }
}
}