# bruteforce algorithmus



## saua (13. September 2005)

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,
> ...




es gäbe ja diese möglichkeit:

```
<?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 (14. September 2005)

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 (14. September 2005)

Versuch mal das hier:


```
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 (14. September 2005)

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


----------

