evilmoe
Oct 08, 2006, updated at Jan 02, 2007 (UTC)
view11285
view14
0
Goto Top

string mischen (alle moeglichkeiten)

GermanQuestionPHPDevelopment
hallo

ich hab mal wieder ein problem oder besser gesagt keine 100% funktionierende lösung. ich möchte gerne einen string in alle möglickeiten zerlegen z.b.

$str = "horror";

als ergebnis möchte ich dann haben "ohrror","horrro" usw solange bis ich alle möglichkeiten habe. ich weiss das ich mit str_shuffle einen string mischen kann allerding selbst in einer schleife die 2000 mal durchlaüft kriege ich nicht alle ergebnisse raus es fehlen immer wieder einzelne.

kennt ihr ne lösung ?
danke!
comment-contentCommentShareShare
Share on Facebook Share on Twitter Share on Reddit Share on Linkedin

Content-Key: 41700

Url: https://administrator.de/contentid/41700

Printed on: April 19, 2024 at 23:04 o'clock

14 Comments
Latest comment
Goto Top
Member: Dani
Dani Oct 08, 2006 at 20:20:28 (UTC)
Goto Top
Hi,
jetzt Frage ich einfach ganz frech: Was hast du vor?? Was willst du realisieren??


Gruß
Dani
Member: EvilMoe
EvilMoe Oct 08, 2006 at 20:22:52 (UTC)
Goto Top
also kein bruteforce :D
man gibt ein wort ein (max 6 zeichen) dann soll der string in alle möglichkeiten zerlegt werden und alle strings die davon in der db vorkommen sollen ausgegeben werden.
sozusagen ein wörterbuch wo man ein wort vorgibt und dann alle wörter ausgegeben werden die aus dem ursprungswort gebildet werden können
Member: filippg
filippg Oct 08, 2006 at 23:53:02 (UTC)
Goto Top
hallo,

das lässt sich mit Rekursion erledigen.

Grob:
string Shuffle (Rekursionstiefe int, BelegtePos int, Ausganswort String){
   if (Rekursionstiefe = 0)
      return new Array();
   String meineTeilstrings = new Array;
   for (int = 0 i; i < Ausgangswort.length(); i++){
      if find(i, BelegtePos)   //überprüft, ob i in BelegtePos vorhanden ist
         break;
      BelegtePos.Add(i);     //fügt i (an der nächsten freien Stelle ein)
      string tiefergelegeneTeilstrings = Shuffle(Rekursionstiefe - 1, BelegtePos, Ausgangswort);
      for(int z; z < tiefergelegeneTeilstrings.size(); z++){
         meineTeilstrings.Add(Ausgangswort[i] + tiefergelegenerTeilstring[z]);
      }
   }
   return meineTeilstrings;
}

Aufruf im Hauptprogramm über
int belgtePos = new Array();
alleKombinationen = Shuffle(meinWort.length(), belegtePos, meinWort);

Ich hoffe, du kennst dich mit Rekursionen ein klein wenig aus? Das Prinzip ist einfach: mich interessiert eigentlich nicht wirklcih, welche Buchstaben ich habe. Ich weiss nur: an jeder Position des Ausgangsworts steht einer, den ich verwenden muss. Oh... dabei fällt mir auf: bei doppelten Buchstaben bekomme ich auch doppelte Wörter... okay, die kann man auf diverse Arten aussortieren. Lässt sich glaube ich nur sehr schwer vermeiden.
Also, es funktioniert so: der erste Aufruf nimmt sich als erstes den ersten Buchstaben im Augsgangswort (fügt ihn bzw. seine Position in BelegtePos ein). Dann ruft er die Funktion rekursiv auf, um für die verbleibenden Stellen (entspricht der Rekursionstiefe, die noch über ist) alle möglichen Kombinationen zu finden. Dies tut er (der erste Aufruf, sprich die oberste Rekursiosebene) in einer Schleife für alle möglichen Buchstaben (entspricht der Länge des Ausgangswortes). An den jeweils bearbeiteten Buchstaben hängt er dann alle möglichen Kombinationen für alle tieferen Rekursionsebenen an. Die jeweils aufgerufenen Rekursionen tuen genau das gleiche: Sie nehmen den ersten freien Buchstaben aus dem Ausgangswort. Da vor ihnen ja schon jede höhere Rekursionsebene einen für sich beansprucht sind nicht mehr alle frei, und sie müssen überprüfen, welche noch zu haben sind (if find(i, BelegtePos)). Zu diesem Buchstaben finden sie alle möglichen restlichen Teilstrings, und hängen sie an ihn an. Das machen sie in einer Schleife über alle möglichen Buchstaben.

Das ganze neigt halt zu einer gewissen kombinatorischen Explosion, wenn ich das nicht ganz falsch sehe ist die Anzahl möglicher Kombinationen gleich der Fakultät der Länge des Ausgangswortes. Und es werden halt ziemlich viele Arrays angelegt und wieder zerstört, das könnte die Speicherverwaltung beanspruchen. Man sollte nochmal über die Wahl der Datentypen nachdenken. Die Übergabe der Parameter muss übrigens immer per Wert erfolgen (call by value, nicht call by reference). Was natürlich den Speicher nicht schont. Ach so, wenn man aus BelegtePos vor jedem return wieder den letzten Wert entfernt kann man den auch einfach per Referenz übergeben (alles andere ist in manchen Sprachen auch etwas aufwendig).

Ach ja, bevor Fragen kommen: Dieser Code ist nicht in irgendeiner mir bekannten Sprache geschrieben, sollte sich aber in die Meisten übersetzen lassen.

Filipp

Edit: was damit natürlich nicht gemacht ist, ist die DB-Anbindung (_bitte_ mach nicht für jedes einzelne Wort eine extra Abfrage). Was sich machen liesse (und ganz lustig wäre), wäre den Algorithmus z.B. direkt in einem MSSQL-Server laufen zu lassen (wie es mit MySQL ist weiss ich nicht). Da könnte man bestimmt auch noch viele schöne Dinge machen, z.B., dass nicht so viele Temporäre Arrays erzeugt werden (tiefergelegeneTeilstrings). Dubletten liessen sich ganz einfach ausschliessen, und man könnte das sehr schön mit den Wörtern aus der DB abgleichen.
Member: EvilMoe
EvilMoe Oct 09, 2006 at 05:05:04 (UTC)
Goto Top
vielen dank! "Ich hoffe, du kennst dich mit Rekursionen ein klein wenig aus?" da muss ich jetzt wohl passen. du hast dir soviel mühe gegeben und ich kann damit fast ganix anfangen ;( vielleciht könntest mir ein komplettes beispiel geben was funktioniert wo ich dann nur das nötigste austauschen muss. zu den problem wenn ein buchstabe doppelt ist kommt auch ein wort oppelt vor ist kein problem da weiss ich wie ich das erledige.
Member: EvilMoe
EvilMoe Oct 10, 2006 at 16:15:22 (UTC)
Goto Top
könnte mir mal sagen wieviel kombinationen bei einen wort überhaupt möglisch wären? bei 3,4,5,6 zeichen?
Member: filippg
filippg Oct 10, 2006 at 17:41:31 (UTC)
Goto Top
könnte mir mal sagen wieviel
kombinationen bei einen wort überhaupt
möglisch wären? bei 3,4,5,6
zeichen?
Meine Schätzung lag ja bei Fakultät(Wortlänge).

Bei Wortlänge = x ist das Zielwort auch x Zeichen lang und es gibt x Buchstaben (Betrachtung von doppelten verkompliziert das ganze deutlich).
Für das erste Zeichen gibt es x Möglichkeiten, für das zweite dann noch x-1, dann x-2, bis x-n=1.
Die Möglichkeiten müssten multipliziert werden, dann ergibt sich x-1 * x-2 * x-3 * ... * 1, was wiederum die Fakultät ist. Auf Taschenrechnern meist mit "!" bezeichnet.

Filipp
Member: Guenni
Guenni Oct 13, 2006 at 11:01:17 (UTC)
Goto Top
@EvilMoe

Hi,

das Zauberwort heißt Permutation

Möglichkeiten=Fakultät(Wortlänge) stimmt nur, wenn keine Buchstaben
doppelt(mehrfach) vorkommen, ansonsten reduziert sich die Anzahl
der Kombinationen.

Das Script:

// Diese Funktion benötigt usort(array,cmp) für den internen Vergleich
function cmp($a,$b){
 if($a==$b) return 0;
 return ($a < $b) ? -1 : 1;
}
// Diese Funktion vertauscht 2 Elemente des Array's 
function swap(&$var,$pos1,$pos2){
 $h=$var[$pos1];
 $var[$pos1]=$var[$pos2];
 $var[$pos2]=$h;
}
// Diese Funktion sortiert das Array neu ab Position pos
function resort(&$var,$pos){
 $ok=true;
 while($ok){
  $ok=false;
	for($i=$pos;$i<count($var)-1;$i++){
	 if($var[$i]>$var[$i+1]){
	  $h=$var[$i];
		$var[$i]=$var[$i+1];
		$var[$i+1]=$h;
		$ok=true;
	 }
	}
 }
}
// Diese Funktion gibt das Array aus
function write_array($var){
 foreach($var as $w){
  echo $w;
 }
 echo "(br)";  
}
// Diese Funktion erzeugt die Permutation 
function permutation(&$var){
 $e1=count($var)-1;
 while($var[$e1]>=$var[$e1+1]){
  if($e1==0){return false;}
	$e1--;
 }
 $e2=count($var)-1;
 while($var[$e2]<=$var[$e1]){
  $e2--;
 }
 swap($var,$e1,$e2);// Gefundene Buchstaben werden getauscht
 resort($var,$e1+1);// Array ab Position e1+1 alphabetisch sortieren
 return true;
}

if($cmd){
 if(!$text){
  echo "Sie müssen ein Wort eingeben! <a href=perm.php>Zurück</a>";  
  exit;
 }
 $wort=array();
 for($i=0;$i<strlen($text);$i++){
  $wort[$i]=$text[$i];
 }

echo "Ausgangsarray: ";  
 write_array($wort);
 usort($wort,cmp); // Die Sortierung in alphabetischer Reihenfolge ist die 1. Permutation....
 $i=1;
 echo "Permutationen:(br)";  
 echo "Permutation $i : ";  
 write_array($wort); // Ausgabe der 1. Permutation

 while(permutation($wort)){  // Ausgabe der restlichen .....
  $i++;
  echo "Permutation $i : ";  
  write_array($wort);
 }
 echo "<hr>";  
 echo "<!--";  
}
?> 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">  

<html>
<head>
<title>Untitled</title>
</head>
<body>
<form action="perm.php" method="post">  
<table border="1" cellpadding="3">   
<tr>
<th colspan="2">Permutations-Demo</th>  
</tr>
<tr>
<td>Ein Wort</td>
<td><input type="text" name="text"></td>  
</tr>
<tr>
<td>Los geht's</td>  
<td align="center"><input type="submit" name="cmd" value="Permutieren"></td>  
</tr>
</table>
</form>
</body>
</html>
<?
if($cmd){
 echo "//-->";  
 echo "Zurück zum Formular <a href=perm.php>Zurück</a>";  
}

Grüße
Günni


PS.: Zeilenumbrüche (br) im Script korrigieren, hier im Kommentar werden die mit spitzen Klammern nicht dargestellt
Member: EvilMoe
EvilMoe Oct 13, 2006 at 13:04:12 (UTC)
Goto Top
danke günni !!!

du hast zwar
$cmd = $_POST['cmd'];  
$text = $_POST['text'];
vergessen aber ist ja nicht schlimm aber wäre es auch möglich das wenn ich als wort hai eingebe mir auch ai , ia usw angezeigt wird?
Member: Guenni
Guenni Oct 13, 2006 at 17:24:29 (UTC)
Goto Top
@EvilMoe

Hi,

$text=$_POST['text']; habe ich nicht vergessen, der Name des Textfeldes kann
als $Name direkt im Script verarbeitet werden. Funktioniert zumindest bei
meinem Webserver.

Was meinst du mit: Wenn ich Hai eingebe, kann ich dann ai oder ia ausgeben lassen?

Willst du beim Ergebnis bestimmte Buchstaben weglassen?

Grüße
Günni
Member: EvilMoe
EvilMoe Oct 13, 2006 at 19:51:15 (UTC)
Goto Top
mhh komisch bei mir funktioniert weder lokal noch auf mein webserver mit $text und $cmd aber ist ja auch kein problem. ne ich will wenn ich ein wort eingebe wirklich alle möglichkeite d.h. wenn ich ein wort mit 6 buchstaben eingebe sollen mir alle kombinationen von 3 bis 6 buchstaben angezeigt werden
Member: Guenni
Guenni Oct 13, 2006 at 23:15:18 (UTC)
Goto Top
@EvilMoe

Hi,

ich weiß ja jetzt nicht, was da bei dir schief läuft mit dem Script.

Ich habe dieses Script 1:1 , also genauso, wie ich es gepostet habe,
mal veröffentlicht --> http://net-comm.de/perm.php

Funkt. einwandfrei.

Grüße
Günni
Member: EvilMoe
EvilMoe Oct 13, 2006 at 23:34:42 (UTC)
Goto Top
ich sage doch nicht dass das script nicht funktioniert es funktoniert wunderbar bei mir! allerdings kriege ich wenn ich ein wort mit 5 buchstaben eingebe auch nur alle kombinationen mit 5 buchstaben. ich möchte aber gerne alle kombinationen mit mindestens 3 buchstaben auch wenn ich ein wort eingebe was schon 5 hat eben alle möglichkeiten
Member: Guenni
Guenni Oct 15, 2006 at 07:42:44 (UTC)
Goto Top
@EvilMoe

Hi,

ich habe das Script umgeändert, so dass zuerst alle Buchstaben
vertauscht werden. Anschließend wird das Wort solange von
vorne gekürzt bis nur noch 2 Buchstaben überbleiben.

Dein Beispiel "Horror":
Horror
orror
rror
ror
or

if($cmd){
 if(!$text || (strlen($text)>6)){
  echo "Sie müssen ein Wort eingeben, max. 6 Buchstaben! <a href=perm2.php>Zurück</a>";  
  exit;
 }
 $wort=array();
 $wort2=array(); // Ein zweites Array
 for($i=0;$i<strlen($text);$i++){
  $wort[$i]=$text[$i];
	$wort2[$i]=$text[$i]; // Das zweite Array bekommt auch das Wort zugewiesen
 }

 // Hier werden die Kombinationsmöglichkeiten
// des kompletten Wortes ausgegeben
 echo "Ausgangsarray: ";  
 write_array($wort);
 usort($wort,cmp);
 $i=1;
 echo "Permutationen:(br)";  
 echo "Permutation $i : ";  
 write_array($wort);
 while(permutation($wort)){
  $i++;
  echo "Permutation $i : ";  
  write_array($wort);
 }
 echo "<hr>";  
// Anschließend wird das zweite Array in einer Schleife solange
// von vorne gekürzt, bis es nur noch 2 Elemente hat.

 for($j=0;$j<strlen($text)-2;$j++){
  array_shift($wort2);  // Erstes Element löschen
	$wort=$wort2; // $wort bekommt das gekürzte Array zugewiesen
  echo "Ausgangsarray: ";  
  write_array($wort);
  usort($wort,cmp);
  $i=1;
  echo "Permutationen:(br)";  
  echo "Permutation $i : ";  
  write_array($wort);
  while(permutation($wort)){
   $i++;
   echo "Permutation $i : ";  
   write_array($wort);
  }
  echo "<hr>";  
 }
 echo "<!--";  
}

Das läßt sich natürlich auch umdrehen.
Wieder dein Beispiel "Horror":
Horror
Horro
Horr
Hor
Ho

Dazu füllst du einfach ein drittes Array

if($cmd){
 if(!$text || (strlen($text)>6)){
  echo "Sie müssen ein Wort eingeben, max. 6 Buchstaben! <a href=perm2.php>Zurück</a>";  
  exit;
 }
 $wort=array();
 $wort2=array();
 $wort3=array();
 for($i=0;$i<strlen($text);$i++){
  $wort[$i]=$text[$i];
	$wort2[$i]=$text[$i];
	$wort3[$i]=$text[$i];
 }
 //Ausgabe des kompletten Worts
 echo "Ausgangsarray: ";  
 write_array($wort);
 usort($wort,cmp);
 $i=1;
 echo "Permutationen:(br)";  
 echo "Permutation $i : ";  
 write_array($wort);
 while(permutation($wort)){
  $i++;
  echo "Permutation $i : ";  
  write_array($wort);
 }
 echo "<hr>";  
 // Ausgabe des Worts, es wird bei jedem Scheifendurchlauf
 // das erste Element des zweiten Arrays gelöscht.
 for($j=0;$j<strlen($text)-2;$j++){
  array_shift($wort2);
	$wort=$wort2;
  echo "Ausgangsarray: ";  
  write_array($wort);
  usort($wort,cmp);
  $i=1;
  echo "Permutationen:(br)";  
  echo "Permutation $i : ";  
  write_array($wort);
  while(permutation($wort)){
   $i++;
   echo "Permutation $i : ";  
   write_array($wort);
  }
  echo "<hr>";  
 }
 // Ausgabe des Worts, es wird bei jedem Scheifendurchlauf
 // das letzte Element des dritten Arrays gelöscht.

 while(count($wort3)>2){
  array_pop($wort3);
	$wort=$wort3;
	echo "Ausgangsarray: ";  
  write_array($wort);
  usort($wort,cmp);
  $i=1;
  echo "Permutationen:(br)";  
  echo "Permutation $i : ";  
  write_array($wort);
  while(permutation($wort)){
   $i++;
   echo "Permutation $i : ";  
   write_array($wort);
  }
  echo "<hr>";  
 }
 echo "<!--";  
}

Grüße
Günni
Member: EvilMoe
EvilMoe Jan 02, 2007 at 17:41:49 (UTC)
Goto Top
Hi Günni.
Nach einer langen Pause melde ich mich mal wieder.
Wäre es zuviel verlang von dir wenn du mir das script so umschreiben könntest das ich 4 arrays habe wo in im jeden array alles kombis drin sind mit der selben wortlänge ?
GermanQuestionPHPDevelopment
Hotly discussed
gleixnerdCheck of ZFW Firewallgleixnerd - 3 CommentsAlexWishaHow to set up and configure a Linux GRE tunnelAlexWisha - 3 CommentsjstrickerWIREGUARD VPN ON UDM PRO BEHIND FRITZBOX - HANDSHAKE DID NOT COMPLETEjstricker - 3 CommentsDaniEnd of Support dates for Office 2016, 2019 Apps und Productivity ServersDani - 1 Comment