Kombinationsmöglichkeiten eines char Arrays berechnen

Naja da dies hier alles irgendwie ausartet und ich(dank volkard & darkfate) schon eine ungefähre Vorstellung habe wie ich mein Problem lösen werde, möchte ich allen(die nicht geflamt haben) danken und bitte um Schließung des Threads bevor es noch weiter ausartet.

MfG Endl

darkfate

Endl schrieb:

Threads bevor es noch weiter ausartet.

Huch?! Im moment ist es doch wieder ruhig?

darkfate schrieb:

krümelkacker schrieb:

..

Immer deine sinnlosen Beiträge.
[...]

Hast Du etwa nach dem "So ein Quatsch!" aufgehört zu lesen? Ich schrieb:

krümelkacker schrieb:

Es kommt auf die Tiefe des "Aufruf-Baums" an und nicht, wieviele "Knoten" der hat, was im übrigen auch nicht n! gewesen wäre. Die Tiefe des "Aufruf-Baums" bei so einem rekursiven Ansatz für das Aufzählen aller Kombinationsmöglichkeiten der Länge n wäre n selbst. Das ist natürlich kein Problem für den automatischen Speicher.

Ich denke, der "Ansatz" ist von Dir gar nicht verstanden worden. Der "rekursive Ansatz" sieht so aus (falls das noch nicht klar sein sollte):

#include <iostream>
#include <cassert>

void aufzaehlen(char* ioptr, const char* from, int sub=0)
{
  if (!*ioptr) {
    std::cout << (ioptr-sub) << '\n';
    return;
  }
  const char* q = from;
  while (*q) {
    *ioptr = *q++;
    aufzaehlen(ioptr+1,from,sub+1);
  }
}

int main()
{
  char puffer[] = "xxx"; // bis zu drei Zeichen ...
  char* p = puffer;
  while (*p) {
    aufzaehlen(p,"ABC"); // ... aus A,B,C
    p++;
  }
}

Wie Du feststellen kannst, ist da die Rekursionstiefe höchstens 3.

darkfate schrieb:

Nenne mir ein einziges Beispiel wo Krümmelkacker nicht beteiligt ist.

??
Ich kann mich jetzt nur an 2 Threads erinnern, wo ich mich Dir gegenüber negativ zu Wort gemeldet habe. Das eine Mal hast Du nachgefragt, wozu das "const" hinter Elementfunktionen gut ist, was man auch alleine hätte rausfinden können und das zweite Mal heute hier, wo Du anscheinend nicht auf diese simple Lösung gekommen bist und etwas von Rekursionstiefe n! erzählen wolltest.

kk

volkard

Endl schrieb:

möchte ich allen(die nicht geflamt haben) danken und bitte um Schließung des Threads bevor es noch weiter ausartet.

Vielen Dank. Wir Mods haben bei sowas immer das Problem, ob wir einen Thread abwürgen, was zwar den Streit (kurzfristig) beendet, aber dem Fragesteller unter Umständen die Lösung entzieht. Jetzt weiß jeder Mod, daß er schließen kann. Nett von Dir. Ich werde auch den Thread nicht nur schließen, sondern sogar ganz löschen, weil er doch ein wenig zu weit danebengeht. Aber noch hoffe ich, daß die Kombattanten sich einigen. Nicht wundern, wenn der Thread plötzlich weg ist.

Endl schrieb:

Naja da dies hier alles irgendwie ausartet und ich(dank volkard & darkfate) schon eine ungefähre Vorstellung habe wie ich mein Problem lösen werde,

Ich würde empfehlen, daß Du nochmal einen Thread startest, in dem Du explizit nach einer Lösung fragst für das Alphabet "ABCDEF" und nur alle achtbuchstabigen Kombinationen. (Kein Witzt, da steckt algorithmisch noch ein Klassiker drin, der saulecker ist.)

darkfate

krümelkacker schrieb:

Hast Du etwa nach dem "So ein Quatsch!" aufgehört zu lesen?

Ja weil es überflüssig war. Es geht auch anders.

krümelkacker schrieb:

Ich denke, der "Ansatz" ist von Dir gar nicht verstanden worden. Der "rekursive Ansatz" sieht so aus (falls das noch nicht klar sein sollte)

Super! Damit wäre ich glücklich. Ich bin kein Programmierer ich hatte keine C/C++ Vorlesung. Gönne mir Fehler!

krümelkacker schrieb:

Ich kann mich jetzt nur an 2 Threads erinnern, wo ich mich Dir gegenüber negativ zu Wort gemeldet habe.

Da haben wir doch schon eins. Du weißt ja, negative Dinge brennen sich sehr einfach ins Gedächtnis. Ich bin eben auf der Suche sogar auf sinnvolle Antworten von dir auf meine Fragen gestoßen. Die hatte ich wohl zuvor im Zorn verdrängt.

krümelkacker schrieb:

was man auch alleine hätte rausfinden können

Es ging darum ob man sich die übrigen const in den Argumenten sparen könnte wenn man hinter die Memberfunktion ein const hat. Die Antwort war nein, das const hinter der Memberfunktion gilt nur für this->Pointer. Dafür habe ich einen ganzen Tag suchen müssen bevor nach vielen Vorwürfen der Untätigkeit der richtige Tipp kam. Total unnötig. Diese schnelle Knappe Antwort von 10sec Aufwand hätte mir die frustrierende Suche erspart.
Alleine wäre ich sicherlich auch nach zwei Tagen nicht drauf gekommen weil ich nach einer anderen Form von Antwort gesucht habe. Zu meiner Frustration kamst auch noch du und behauptest ich sei zu faul selber zu suchen. Ich habe es ja versucht zu erklären aber es war fruchtlos.

krümelkacker schrieb:

und das zweite Mal heute hier, wo Du anscheinend nicht auf diese simple Lösung gekommen bist und etwas von Rekursionstiefe n! erzählen wolltest.

Es ist nunmal so das man eine Lösung unendlich kompliziert gestalten kann. Ich habe, ohne viel Zeit dafür zu investieren, schnell eine Skizze gemacht und bin auf eine Tiefe von n! gekommen, dafür konnte ich im Moment nichts. Keine gute Lösung, aber auch kein Grund mich so anzufahren. Weil ich mich schon mit einer anderen/besseren Lösung beschäftigt habe (steht irgendwo oben), ließ ich kurz ein Kommentar los damit er sieht das man seine Frage zur Kenntnis genommen hat. Damit hatte er auch eine Richtung in die er schonmal anfangen könnte.

knivil

rekursiv iterieren

Was denn nun, Rekursion oder Iteration?

Ich hatte Zorn

Siehst du, hilft absolut ueberhaupt nicht.

warum hat bisher eigtl niemand std::next_permutation vorgeschlagen?

Weil das nicht die Loesung des Problems ist.

Und hier die ultimative Loesung in Haskell mit purer REKURSION. Die Laenge der Liste entspricht der Rekursionstiefe.

fun 1 ls = map (\x -> [x]) ls
fun n ls = a ++ concatMap (\x -> map (\y ->y:x) ls) a
  where a = fun (n-1) ls

realFun ls = fun (length ls) ls

realFun "ABC"  fuehrt zu 48 Elementen als Ausgabe

Man braucht halt drei Arrays mit n³-2n²+n Elementen. Dürfte theoretisch besser sein als andauern Rücksprungadressen auf dem Stack abzulegen.

Das bezweifle ich. Wie sieht dein Ansatz mit "ABCDE" oder laengeren Zeichenketten aus?

darkfate

knivil schrieb:

Was denn nun, Rekursion oder Iteration?

Rekursiv iterieren

knivil

Es ist aber auch kein Freischein andere Leute absolut zu unrecht anzupöbeln.

Willkommen im Internet.

Wer hat zuerst angefangen zu pöbeln?

Kleinkind?

Er hat nur einfach keine gute Erziehung genossen. In realem Umfeld wäre es sehr unangenehm für Ihn so einen Unfug von sich zu lassen.

Ueberlasse die Erziehung doch anderen, ein Forum ist dafuer wohl das ungeeignetste Medium.

PS: Zu Iteration gehoeren Iterationskonstrukte wie for oder while, im Allgemeinen werden sie auch Schleifen genannt und unterscheiden sich allein dadurch von Rekursion. Jedoch kann mittels Rekursion Iteration nachgebildet werden. Daraus ergibt sich a)es ist doppelt gemoppelt, was du schreibst oder b) komplett widerspruechlich.

darkfate

knivil schrieb:

Willkommen im Internet.

Kleinkind?

Ueberlasse die Erziehung doch anderen, ein Forum ist dafuer wohl das ungeeignetste Medium.

Och komm, mir geht es gerade so gut. Wir müssen das jetzt nicht noch einmal durchdiskutieren. Ich habe auch schon aus diesem Grund aufgehört Fragen zu stellen falls ich mal was nicht verstehe.. es muss nicht noch weiter gehen.

knivil schrieb:

PS: Zu Iteration gehoeren Iterationskonstrukte wie for oder while, im Allgemeinen werden sie auch Schleifen genannt und unterscheiden sich allein dadurch von Rekursion.

Richtig. Wenn man jedoch eine Rekursion hat über der eine Schleife hängt, dann iteriert man rekursiv.

// Schleife
for(i=0;i<n;i++){
  char *tmpword = malloc((i+1)*sizeof(char));
  t=0;
  tmpword = substr(wort,0,i+1);
  // Rekursion
  permutiere(tmpword,tmpword);
}

knivil

darkfate schrieb:

Wenn man jedoch eine Rekursion hat über der eine Schleife hängt, dann iteriert man rekursiv.

Alles das sollte man aus deinem ersten Post mit dieser Formulierung herauslesen. Sorry.

darkfate

knivil schrieb:

Alles das sollte man aus deinem ersten Post mit dieser Formulierung herauslesen.

Den anfänglichen Buchstabensalat wird man wohl am einfachsten mit einer Iteration lösen, bis es zur voller Wortgröße kommt.

A
AB
BA
--- // Mir fällt jetzt nichts ein wie es bis hier ohne zu iterieren kurz zu lösen wäre.
ABC

Der interessante Teil kommt sowieso erst in der vollen Wortgröße.
Bis gestern Abend habe ich die ersten beiden Arrays hinbekommen..
vielleicht komme ich heute Abend dazu es zu beenden falls überhaupt noch Interesse besteht es ohne Rekursionen zu lösen.

knivil schrieb:

Sorry.

Wofür? Man wird sich doch wohl das Recht haben, kritisch zu hinterfragen? So empfindlich bin ich doch gar nicht.