kompliziert

[frank]

Hallo Leute

Hab folgendes Problem:

1.
eine Variable $anzahl bekommt durch einen benutzer eine Zahl  >=1      zugewiesen.
z.B. $anzahl= 3;

2.
Nun sollen alle möglichen Strings der länge 3 (da $anzahl= 3) erzeugt werden in denen die Buchstaben a-z vorkommen dürfen.
z.B.

aaa, aab, aac, ... , aaz
aba, abb, abc, ... , abz
aca, acb, acc, ... , acz
.
.
.
aza, azb, azc, ... , azz
.
.
.
.................. , zzz

einfach gesagt, alle kombinationen von "aaa" bis "zzz"
bei $anzahl= 4 natürlich von "aaaa" bis "zzzz"

-----------------------------------------
Problem

Ich kann die kombinationen zwar erzeugen aber nur wenn $anzahl immer gleich ist.
Damit meine ich wenn $anzahl z.b immer 2 wäre, brauch ich 2 Schleifen.

Beispiel: (für einen String der Länge 2)

$para_2= 97;   //97 entspricht "a" (ASCII)
for(P_2= 1; $p_2 <=26; P_2++)
{
 $para_1 = 97;
 for($p_1= 1; $p_1 <= 26; $p_++)  //26 mal wegen 26 Buchstaben
 {
  // Anweisungen: umwandeln von ASCII in Buchstaben
  echo $para_2;
                echo 2$para_1<br>";
                // Anweisungen: umwandeln von Buchstaben in ASCII

$para_1++;
 }
 $Para_2++;
}

Will ich jetzt nen String der Länge 3 brauch ich noch eine Schleife!

Wie kann ich das jetzt Aber 'dynamisch' also in Abhängigkeit von der Länge des Stings machen?

Bin für jede Hilfe dankbar!
Soll ja nicht gleich ein fertiger code sein, freu mich auch über ansätze oder vorschläge

vielleicht denke ich nur zu kompliziert weil ich vorher viel c gemacht habe und erst seit ner woche php.

Hab sehr lange überlegt und immer hat irgendwas nicht funktioniert.

Gruß und danke,
Frank

[Sven Rautenberg]

Moin!

Nun sollen alle möglichen Strings der länge 3 (da $anzahl= 3) erzeugt werden in denen die Buchstaben a-z vorkommen dürfen.

vielleicht denke ich nur zu kompliziert weil ich vorher viel c gemacht habe und erst seit ner woche php.

Hab sehr lange überlegt und immer hat irgendwas nicht funktioniert.

Wenn du alle "Worte" von aaa bis zzz ausgeben willst, dann ist diese Aufgabe eigentlich dasselbe, als wenn du alle "Zahlen" von 000 bis 999 ausgeben willst.

Mit dem Unterschied, dass du beim Schritt "addiere 1" bei den Worten die Addition inklusive des Übertrags auf die nächsthöhere Stelle selbst erledigen mußt, während der Computer das bei der mathematischen Rechnung "plus 1" bei den Zahlen automatisch tut.

- Sven Rautenberg

[Frank]

Danke schonmal Sven

Genau das hab ich mir auch schon überlegt.
Es ist dann quasi ein zahlensystem zur basis 26.

Weiß aber nicht wie ich bei einem übertrag die vorherigen stellen wieder zurücksetzten soll.

Also   1 | 1 | 26    //wenn 26 dann erhöhe nächste stelle um 2
       a | a | z     //und setze 26 zurück auf 1

dann   1 | 2 | 1
       a | b | a

und das alles in abhängigkeit von der Länge

puh, naja werd mal weiter tüfteln :)

[Sven Rautenberg]

Moin!

Genau das hab ich mir auch schon überlegt.
Es ist dann quasi ein zahlensystem zur basis 26.

Weiß aber nicht wie ich bei einem übertrag die vorherigen stellen wieder zurücksetzten soll.

Ist doch eigentlich simpel. Für jede Stelle benötigst du eine Int-Variable (in PHP gibts zwar keine Typen, aber zur Verdeutlichung sei's gesagt). Da du grundsätzlich variable Stellenlängen willst, bietet sich ein Array an. Der Arrayindex beziffert die Stelle, Index 0 ist die erste Stelle, Index 1 die zweite usw.

Der Variableninhalt jeder Stelle wird mit 0 initialisiert.

Und jetzt addierst du zur ersten Stelle eine 1.

Und dann guckst du, ob die erste Stelle überläuft, d.h. der gespeicherte Wert gleich ist mit der Anzahl der möglichen Symbole (bei dir: 26 Buchstaben). Dann: Diese Stelle zurück auf 0 setzen, nächste Stelle um 1 erhöhen.

Und solange du Stellen hast, die überlaufen, solange prüfst du dann die nächsthöhere Stelle.

Damit hast du dann dein Zählersystem hergestellt. Der davon unabhängige Teil ist, dass an irgendeiner Stelle dieser Schleife eine Ausgabe erfolgen soll.. Die Ausgabe realisierst du vielleicht so, dass du eine feste Formel oder Zuordnung wählst, um aus einem Zählerwert ein Symbol zu machen,

Bei deiner einfachen Buchstabenausgabe wäre das z.B. "Zählerwert plus 65 = ASCII-Wert". Man könnte sich aber auch ein Lookup-Array denken, das einmal initialisiert wird, und in dem zu jedem Zählerindex die vorzunehmende Ausgabe steht. Wenn beispielsweise die Ausgabe als Grafik passieren soll, würde in diesem Array das <img>-Element als String abgelegt sein (sofern es keine simplere Methode gibt, weil z.B. die Zählernummer in der Bild-URL auftaucht).

- Sven Rautenberg

[bleicher]

Wenn beispielsweise die Ausgabe als Grafik passieren soll, würde in diesem Array das <img>-Element als String abgelegt sein (sofern es keine simplere Methode gibt, weil z.B. die Zählernummer in der Bild-URL auftaucht).

oder man lädt alphabet in Array ab und läuft den loop mit $anzahl durchläufen um dem string $anzahl mal die buchstabe aus dem array mit dem zahlwert des ausgbenindex zu addieren?

MFG
bleicher

[Sven Rautenberg]

Moin!

Wenn beispielsweise die Ausgabe als Grafik passieren soll, würde in diesem Array das <img>-Element als String abgelegt sein (sofern es keine simplere Methode gibt, weil z.B. die Zählernummer in der Bild-URL auftaucht).

oder man lädt alphabet in Array ab und läuft den loop mit $anzahl durchläufen um dem string $anzahl mal die buchstabe aus dem array mit dem zahlwert des ausgbenindex zu addieren?

Hä?

- Sven Rautenberg

[Fank]

Ok gut.
Sehr gute Erklärung, echt!! TOP!

Werd das heute abend versuchen und wenn alles klappt post ichs mal hier, dann kannst dus ja mal anschaun wenn du willst..

schönen Tag noch und Danke!

[Matti Maekitalo]

Tauch auch.

Nun sollen alle möglichen Strings der länge 3 (da $anzahl= 3) erzeugt werden in denen die Buchstaben a-z vorkommen dürfen.

Am einfachsten ist ne rekursive Funktion, welcher du $anzahl mitübergibst und beim übergeben auf die nächste Rekursionsstufe eins runterzählst. Wenn der Timer bei 0 (bzw 1, je nach Implementierung) ankommt, gibst du den gesammelten String aus.

Hier ne einfache Implementation aus dem Kopf mit Zahlen statt Buchstaben.

function rec_numbers($string, $anzahl) {
  for ($i = 0; $i < 26; ++$i) {
    if ($anzahl == 0)
     echo $string . ',' . $i;
    else
     rec_number($string . ',' . $i, $anzahl-1);
  }
}

Habs net getestet, aber hoffentlich sieht man das Prinzip.

Bis die Tage,
Matti

[Frank]

Danke Matti,
Das ist wahrscheinlich die schnellste möglichkeit.
Aber das rekursive programmieren ist irgendwie sehr verwirrend :)
Werds aber trotzdem mal versuchen.

[Sven Rautenberg]

Moin!

Danke Matti,
Das ist wahrscheinlich die schnellste möglichkeit.

Es ist die Möglichkeit, die am meisten Stack-Speicher verbraucht, ja.

Aber das rekursive programmieren ist irgendwie sehr verwirrend :)

Man kann jedes iterative Problem mit einer Rekursion versuchen zu lösen. Man kann auch jedes rekursive Problem durch eine Iteration versuchen zu lösen.

Viele Probleme sind vom Typ her iterativ. Einige sind rekursiv. Absichtlich jeweils das andere Lösungsschema zu verwenden ist nicht wirklich zielführend, und oftmals deutlich aufwendiger.

- Sven Rautenberg

[Matti Maekitalo]

Tauch auch.

Das ist wahrscheinlich die schnellste möglichkeit.
Aber das rekursive programmieren ist irgendwie sehr verwirrend :)
Werds aber trotzdem mal versuchen.

Nunja, Sven hat ja bereits geschrieben, dass es eine einfache, wenn auch nicht unbedingt Ressourcensparende Möglichkeit ist.

Ebenfalls richtig ist, dass es iterative Lösungen für das Problem gibt. Mein Code hat halt 26^n Funktionsaufrufe der rekursiven Funktion, was halt für große n sehr schnell sehr groß wird.

Eine einfache Möglichkeit, rekursive Funktionen selbst zu bauen, ist die Antwort auf die Frage, wie man das Ursprungsproblem (welches eine gewisse "Kardinalität" besitzt (hier die Anzahl der Buchstaben)) auf ein Problem mit einer geringeren Ordnung zurückzuführen. In diesem Fall setzt die rekursive Funktion nacheinander einen Buchstaben und ruft sich dann selbst wieder auf mit der Aufforderung, Buchstaben anzuhängen, aber diesmal eben einen weniger.

Bis die Tage,
Matti

[phpnoob]

Tag

$a= 5;
   for($k=0; $k<$a; $k++) $b.="a";
   $anz= pow(26,$a);
   for($k=0; $k<$a; $k++) $b++;

dabei ist $a deine länge,
          $k zähler für die for-schleifen
und in    $b ist dein string

in die zweite for-schleife kommen deine anweisungen z.b. echo $b;

Wer noch einen schnelleren code schreiben kann, ist besser als die besten!!

Gruß   :-)

[Steel]

Hi,

korrigier mich bitte, aber das hier:

$a= 5;
   for($k=0; $k<$a; $k++) $b.="a";
   $anz= pow(26,$a);
   for($k=0; $k<$a; $k++) $b++;

macht nicht wirklich was, oder?

Du erstellts einen String: 'aaaaa'.
Du rechnest die Anzahl der Moeglichkeiten aus: 26 hoch 5 = 11881376
Du erhoehst den String 'aaaaa' 5x um 1.... -.-'

Hast Du was vergessen, oder uebersehe ich da was wichtiges? *wunder*

[phpnoob]

Sorry, hast natürlich recht, hab nen Tippfehler.
Du musst $anz in &a ändern.
War wohl vorher mit einer Variablen $anz beschäftigt.

$a= 5;
   for($k=0; $k<$a; $k++) $b.="a";

$a= pow(26,$a);

for($k=0; $k<$a; $k++) $b++;

Man muss nur die länge des Strings angeben($a= 5;)
Dann berechnet er wie Frank wollte alle Möglichkeiten.

und in die zweite Schleife eben die Anweisungen reinpacken.

Gruß

[Schieter]

<?php

Rekursive Funktion

function Combi_r($str, $len){
    for($i = 97; $i < 123; $i++){
      $tstr = $str.chr($i);
      if(strlen($tstr) < $len){
        $tstr = Combi_r($tstr, $len);
      }
      print $tstr.'<br>';
    }
  }

Aufruf der Funktion mit der Anzahl der Stringlänge

Combi_r('', 3);
?>