bruteforce algorithmus

saua

Grünschnabel
besser wie hier kann ichs auch nicht sagen:
(hab des in nem andren forum gefunden aber noch immer kein lösung weil ich auch dasselbe problem hab!)

Ich möchte aus 6 frei wählbaren Zeichen (Variablen-->Buchstaben, Zahlen) alle möglichen Kombinationen ausgeben lassen.
z.B (hier nur 3).

vorgegeben: A, B, C,

Ausgabe:

ABC
ACB
BAC
BCA
CAB
CBA

Gibt es unter php eine Funktion welche diesen Job erledigt?


es gäbe ja diese möglichkeit:
PHP:
<?php
// von diesem Bereich
$from = "aaa";
// bis zu diesem Breich
$to   = "zzz";

// Die Kombinationen ausgeben
for($i=$from; $i<=$to; $i++) {
    echo $i;
    echo "<br />";
}
?>

nur diese hat für mich keinen sinn da ich frei wählbare zeiechen hab und da möcht ich alle möglichen kombinationen mit ner liste vergleichen und wenn es eine übereinstimmung gibt dann solls mir das wort ausgeben! also sozusagen bruteforce methode...

danke im vorraus!
mfg!
saua
 

vop

Erfahrenes Mitglied
Hi

ich würde versuchen, rekursiv an die Sache heran zu gehen, etwa so

Ergebnis der Permutation ist jeweils eine Zeichenkette, in der mit Trennzeichen getrennt alle Kombinationen enthalten sind.

Nun definierst du die Permutation so
Permutation( $Zeichenfolge, $Trennzeichen)
= $Zeichenfolge, wenn strlen($Zeichenfolge)<=1
sonst
Trenne erstes Zeichen von $Zeichenfolge ab, Permuttiere die Restzeichenfolge
und kombiniere das erste Zeichen mit allen Teilzeichenfolgen der Permuttation

Beim Kombinieren einer Teilzeichenfolge soll sowas rauskommen (; als Trennzeichen)
kombiniere( '1', '234', ';' ) => '1234;2134;2314;2341'

Hilft dir das als Ansatz weiter?
vop
 

vop

Erfahrenes Mitglied
Versuch mal das hier:

Code:
 function Perm1Zeichen( $Zeichen, $Zeichenfolge, $Trennzeichen )
   {
 	$Ergebnis = $Zeichen . $Zeichenfolge;
 	for ( $i=0; $i<strlen($Zeichenfolge);$i++)
 	{
 	  $Ergebnis .= $Trennzeichen . substr($Zeichenfolge,0,$i+1) .$Zeichen . substr( $Zeichenfolge,$i+1,strlen($Zeichenfolge)-1);
 	};
 	return $Ergebnis;
   };
   function Permuttiere( $Zeichenfolge, $Trennzeichen )
   {
 	$Len		= strlen( $Zeichenfolge );
 	if ( $Len > 1 )
 	{
 	  $Zeichen1   = substr( $Zeichenfolge,0,1);
 		$Rest	   = substr( $Zeichenfolge,1,$Len-1);
 	  $Permutation= Permuttiere( $Rest, $Trennzeichen );
 	  $Kombination= explode( $Trennzeichen, $Permutation);
 	  $Ergebnis = '';
 	  foreach( $Kombination as $Variante)
 	  {
 		if ( $Ergebnis !='')
 		{
 		  $Ergebnis.=$Trennzeichen;
 		};
 		$Ergebnis.= Perm1Zeichen($Zeichen1,$Variante,$Trennzeichen);
 	  };
 	}
 	else
 	{
 	  $Ergebnis = $Zeichenfolge;
 	};
 	return $Ergebnis;
   };

Sollte helfen.
Du rufst Permuttiere( $Zeichenfolge, $Trennzeichen ) auf
und erhälst einen String, der durch Trennzeichen getrennte Permuttationen der Zeichenfolge enthält. Den kannst du mit explode in einzelne Strings zerlegen

vop
 

vop

Erfahrenes Mitglied
Noch ein Nachtrag

Bereits mit einer 10-Zeichen langen Zeichenfolge hat sich das System bei mir mit einem Segmentation fault abgemeldet. Naja, 10! = 362880 verschieden Kombinationen mit jeweils 10 (+1 für Trennzeichen) Zeichen ergibt halt einen String der Länge 39916800 Bytes.

Also brute force wird seinem Namen da gerecht. :)

vop