Top-Themen

AppleEntwicklungHardwareInternetLinuxMicrosoftMultimediaNetzwerkeOff TopicSicherheitSonstige SystemeVirtualisierungWeiterbildungZusammenarbeit

Aktuelle Themen

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit

string mischen (alle moeglichkeiten)

Frage Entwicklung PHP

Mitglied: EvilMoe

EvilMoe (Level 2) - Jetzt verbinden

08.10.2006, aktualisiert 02.01.2007, 7367 Aufrufe, 14 Kommentare

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!
Mitglied: Dani
08.10.2006 um 22:20 Uhr
Hi,
jetzt Frage ich einfach ganz frech: Was hast du vor?? Was willst du realisieren??


Gruß
Dani
Bitte warten ..
Mitglied: EvilMoe
08.10.2006 um 22:22 Uhr
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
Bitte warten ..
Mitglied: filippg
09.10.2006 um 01:53 Uhr
hallo,

das lässt sich mit Rekursion erledigen.

Grob:
01.
string[] Shuffle (Rekursionstiefe int, BelegtePos int[], Ausganswort String){ 
02.
   if (Rekursionstiefe = 0) 
03.
      return new Array(); 
04.
   String[] meineTeilstrings = new Array; 
05.
   for (int = 0 i; i < Ausgangswort.length(); i++){ 
06.
      if find(i, BelegtePos)   //überprüft, ob i in BelegtePos vorhanden ist 
07.
         break; 
08.
      BelegtePos.Add(i);     //fügt i (an der nächsten freien Stelle ein) 
09.
      string[] tiefergelegeneTeilstrings = Shuffle(Rekursionstiefe - 1, BelegtePos, Ausgangswort); 
10.
      for(int z; z < tiefergelegeneTeilstrings.size(); z++){ 
11.
         meineTeilstrings.Add(Ausgangswort[i] + tiefergelegenerTeilstring[z]); 
12.
13.
14.
   return meineTeilstrings; 
15.
16.
 
17.
Aufruf im Hauptprogramm über 
18.
int[] belgtePos = new Array(); 
19.
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.
Bitte warten ..
Mitglied: EvilMoe
09.10.2006 um 07:05 Uhr
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.
Bitte warten ..
Mitglied: EvilMoe
10.10.2006 um 18:15 Uhr
könnte mir mal sagen wieviel kombinationen bei einen wort überhaupt möglisch wären? bei 3,4,5,6 zeichen?
Bitte warten ..
Mitglied: filippg
10.10.2006 um 19:41 Uhr
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
Bitte warten ..
Mitglied: Guenni
13.10.2006 um 13:01 Uhr
@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:

01.
// Diese Funktion benötigt usort(array,cmp) für den internen Vergleich 
02.
function cmp($a,$b){ 
03.
 if($a==$b) return 0; 
04.
 return ($a < $b) ? -1 : 1; 
05.
06.
// Diese Funktion vertauscht 2 Elemente des Array's 
07.
function swap(&$var,$pos1,$pos2){ 
08.
 $h=$var[$pos1]; 
09.
 $var[$pos1]=$var[$pos2]; 
10.
 $var[$pos2]=$h
11.
12.
// Diese Funktion sortiert das Array neu ab Position pos 
13.
function resort(&$var,$pos){ 
14.
 $ok=true; 
15.
 while($ok){ 
16.
  $ok=false; 
17.
	for($i=$pos;$i<count($var)-1;$i++){ 
18.
	 if($var[$i]>$var[$i+1]){ 
19.
	  $h=$var[$i]; 
20.
		$var[$i]=$var[$i+1]; 
21.
		$var[$i+1]=$h
22.
		$ok=true; 
23.
24.
25.
26.
27.
// Diese Funktion gibt das Array aus 
28.
function write_array($var){ 
29.
 foreach($var as $w){ 
30.
  echo $w
31.
32.
 echo "(br)"
33.
34.
// Diese Funktion erzeugt die Permutation  
35.
function permutation(&$var){ 
36.
 $e1=count($var)-1; 
37.
 while($var[$e1]>=$var[$e1+1]){ 
38.
  if($e1==0){return false;} 
39.
	$e1--; 
40.
41.
 $e2=count($var)-1; 
42.
 while($var[$e2]<=$var[$e1]){ 
43.
  $e2--; 
44.
45.
 swap($var,$e1,$e2);// Gefundene Buchstaben werden getauscht 
46.
 resort($var,$e1+1);// Array ab Position e1+1 alphabetisch sortieren 
47.
 return true; 
48.
49.
 
50.
if($cmd){ 
51.
 if(!$text){ 
52.
  echo "Sie müssen ein Wort eingeben! <a href=perm.php>Zurück</a>"
53.
  exit
54.
55.
 $wort[]=array(); 
56.
 for($i=0;$i<strlen($text);$i++){ 
57.
  $wort[$i]=$text[$i]; 
58.
59.
 
60.
echo "Ausgangsarray: "
61.
 write_array($wort); 
62.
 usort($wort,cmp); // Die Sortierung in alphabetischer Reihenfolge ist die 1. Permutation.... 
63.
 $i=1; 
64.
 echo "Permutationen:(br)"
65.
 echo "Permutation $i : "
66.
 write_array($wort); // Ausgabe der 1. Permutation 
67.
 
68.
 while(permutation($wort)){  // Ausgabe der restlichen ..... 
69.
  $i++; 
70.
  echo "Permutation $i : "
71.
  write_array($wort); 
72.
73.
 echo "<hr>"
74.
 echo "<!--"
75.
76.
?>  
77.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
78.
 
79.
<html> 
80.
<head> 
81.
<title>Untitled</title> 
82.
</head> 
83.
<body> 
84.
<form action="perm.php" method="post"
85.
<table border="1" cellpadding="3">  
86.
<tr> 
87.
<th colspan="2">Permutations-Demo</th> 
88.
</tr> 
89.
<tr> 
90.
<td>Ein Wort</td> 
91.
<td><input type="text" name="text"></td> 
92.
</tr> 
93.
<tr> 
94.
<td>Los geht's</td> 
95.
<td align="center"><input type="submit" name="cmd" value="Permutieren"></td> 
96.
</tr> 
97.
</table> 
98.
</form> 
99.
</body> 
100.
</html> 
101.
<? 
102.
if($cmd){ 
103.
 echo "//-->"
104.
 echo "Zurück zum Formular <a href=perm.php>Zurück</a>"
105.
}
Grüße
Günni


PS.: Zeilenumbrüche (br) im Script korrigieren, hier im Kommentar werden die mit spitzen Klammern nicht dargestellt
Bitte warten ..
Mitglied: EvilMoe
13.10.2006 um 15:04 Uhr
danke günni !!!

du hast zwar
01.
$cmd = $_POST['cmd']; 
02.
$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?
Bitte warten ..
Mitglied: Guenni
13.10.2006 um 19:24 Uhr
@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
Bitte warten ..
Mitglied: EvilMoe
13.10.2006 um 21:51 Uhr
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
Bitte warten ..
Mitglied: Guenni
14.10.2006 um 01:15 Uhr
@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
Bitte warten ..
Mitglied: EvilMoe
14.10.2006 um 01:34 Uhr
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
Bitte warten ..
Mitglied: Guenni
15.10.2006 um 09:42 Uhr
@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

01.
if($cmd){ 
02.
 if(!$text || (strlen($text)>6)){ 
03.
  echo "Sie müssen ein Wort eingeben, max. 6 Buchstaben! <a href=perm2.php>Zurück</a>"
04.
  exit
05.
06.
 $wort=array(); 
07.
 $wort2=array(); // Ein zweites Array 
08.
 for($i=0;$i<strlen($text);$i++){ 
09.
  $wort[$i]=$text[$i]; 
10.
	$wort2[$i]=$text[$i]; // Das zweite Array bekommt auch das Wort zugewiesen 
11.
12.
 
13.
 // Hier werden die Kombinationsmöglichkeiten 
14.
// des kompletten Wortes ausgegeben 
15.
 echo "Ausgangsarray: "
16.
 write_array($wort); 
17.
 usort($wort,cmp); 
18.
 $i=1; 
19.
 echo "Permutationen:(br)"
20.
 echo "Permutation $i : "
21.
 write_array($wort); 
22.
 while(permutation($wort)){ 
23.
  $i++; 
24.
  echo "Permutation $i : "
25.
  write_array($wort); 
26.
27.
 echo "<hr>"
28.
// Anschließend wird das zweite Array in einer Schleife solange 
29.
// von vorne gekürzt, bis es nur noch 2 Elemente hat. 
30.
 
31.
 for($j=0;$j<strlen($text)-2;$j++){ 
32.
  array_shift($wort2);  // Erstes Element löschen 
33.
	$wort=$wort2; // $wort bekommt das gekürzte Array zugewiesen 
34.
  echo "Ausgangsarray: "
35.
  write_array($wort); 
36.
  usort($wort,cmp); 
37.
  $i=1; 
38.
  echo "Permutationen:(br)"
39.
  echo "Permutation $i : "
40.
  write_array($wort); 
41.
  while(permutation($wort)){ 
42.
   $i++; 
43.
   echo "Permutation $i : "
44.
   write_array($wort); 
45.
46.
  echo "<hr>"
47.
48.
 echo "<!--"
49.
}
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

01.
if($cmd){ 
02.
 if(!$text || (strlen($text)>6)){ 
03.
  echo "Sie müssen ein Wort eingeben, max. 6 Buchstaben! <a href=perm2.php>Zurück</a>"
04.
  exit
05.
06.
 $wort=array(); 
07.
 $wort2=array(); 
08.
 $wort3=array(); 
09.
 for($i=0;$i<strlen($text);$i++){ 
10.
  $wort[$i]=$text[$i]; 
11.
	$wort2[$i]=$text[$i]; 
12.
	$wort3[$i]=$text[$i]; 
13.
14.
 //Ausgabe des kompletten Worts 
15.
 echo "Ausgangsarray: "
16.
 write_array($wort); 
17.
 usort($wort,cmp); 
18.
 $i=1; 
19.
 echo "Permutationen:(br)"
20.
 echo "Permutation $i : "
21.
 write_array($wort); 
22.
 while(permutation($wort)){ 
23.
  $i++; 
24.
  echo "Permutation $i : "
25.
  write_array($wort); 
26.
27.
 echo "<hr>"
28.
 // Ausgabe des Worts, es wird bei jedem Scheifendurchlauf 
29.
 // das erste Element des zweiten Arrays gelöscht. 
30.
 for($j=0;$j<strlen($text)-2;$j++){ 
31.
  array_shift($wort2); 
32.
	$wort=$wort2
33.
  echo "Ausgangsarray: "
34.
  write_array($wort); 
35.
  usort($wort,cmp); 
36.
  $i=1; 
37.
  echo "Permutationen:(br)"
38.
  echo "Permutation $i : "
39.
  write_array($wort); 
40.
  while(permutation($wort)){ 
41.
   $i++; 
42.
   echo "Permutation $i : "
43.
   write_array($wort); 
44.
45.
  echo "<hr>"
46.
47.
 // Ausgabe des Worts, es wird bei jedem Scheifendurchlauf 
48.
 // das letzte Element des dritten Arrays gelöscht. 
49.
 
50.
 while(count($wort3)>2){ 
51.
  array_pop($wort3); 
52.
	$wort=$wort3
53.
	echo "Ausgangsarray: "
54.
  write_array($wort); 
55.
  usort($wort,cmp); 
56.
  $i=1; 
57.
  echo "Permutationen:(br)"
58.
  echo "Permutation $i : "
59.
  write_array($wort); 
60.
  while(permutation($wort)){ 
61.
   $i++; 
62.
   echo "Permutation $i : "
63.
   write_array($wort); 
64.
65.
  echo "<hr>"
66.
67.
 echo "<!--"
68.
}
Grüße
Günni
Bitte warten ..
Mitglied: EvilMoe
02.01.2007 um 18:41 Uhr
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 ?
Bitte warten ..
Neuester Wissensbeitrag
Windows 10

Powershell 5 BSOD

Tipp von agowa338 zum Thema Windows 10 ...

Ähnliche Inhalte
C und C++
gelöst Anzahl der Buchstaben in einem String Element Array C++ (3)

Frage von Protected zum Thema C und C ...

C und C++
String einlesen in Array und wieder ausgeben von hinten (4)

Frage von Protected zum Thema C und C ...

Batch & Shell
gelöst Poweshell Script soll String ersetzen und die leere Zeile löschen (4)

Frage von Mars123 zum Thema Batch & Shell ...

Heiß diskutierte Inhalte
Windows Userverwaltung
Ausgeschiedene Mitarbeiter im Unternehmen - was tun mit den AD Konten? (34)

Frage von patz223 zum Thema Windows Userverwaltung ...

LAN, WAN, Wireless
gelöst Server erkennt Client nicht wenn er ausserhalb des DHCP Pools liegt (28)

Frage von Mar-west zum Thema LAN, WAN, Wireless ...

Windows Server
Server 2008R2 startet nicht mehr (Bad Patch 0xa) (18)

Frage von Haures zum Thema Windows Server ...