Php Array Permutation nach festen Muster

[Rolf B]

Hallo Simone,

okay - aber wie ist denn diese $data-Bombe in deinem Beitrag von 21.10.2018 20:42 zu Stande gekommen? Hast Du die von Hand erzeugt? Oder tatsächlich einen Permutationengenerator laufen lassen? Das sieht sehr aufwändig aus.

Ich habe das Ding heute morgen "mal eben" programmiert, bei mir lokal, daher stammt die Ausgabe aus meinem obigen Beitrag, von daher habe ich eine Vorstellung davon wie man es machen könnte.

Du hast geschrieben dass es eine Referenzwörterliste gibt. Die filterst Du, und merkst Dir die Anfangspositionen. Hat Du bedacht, dass Du mehr als einen Treffer haben kannst? Wenn "au" ein erlaubtes Teilwort wäre, dann hättest Du das in deinem Index an zwei Positionen zu speichern.

Diese $data-Array müsstest Du dann eigentlich nicht in geschachtelten Schleifen abtasten, sondern rekursiv.

Bei mir sieht das so aus - und übrigens kann man in PHP strukturierte Array auch erzeugen ohne die Runde über JSON zu drehen.

$zielwort = "hotelfachfrau";
$index = [ 0 => [ "hot", "hotel", "hotelfach", "hotelfachfrau"],
           2 => [ "tel"],
           3 => [ "elf"],
           5 => [ "fach", "fachfrau"],
           6 => [ "ach"],
           9 => [ "frau" ],
           10 => [ "rau" ]
         ];

$chains = [];
$teilworte = [];
try_at_position(0, $teilworte, strlen($zielwort), $index, $chains);

try_at_position ist eine rekursive Funktion, die an Hand des Index eine Kette aus Teilworten aufbaut bis die gewünschte Ziellänge erreicht ist. Da der Index angibt, ab welcher Position welche Teilworte beginnen, ist das eigentlich nicht schwierig. Der Trick ist der partChain-Parameter, wo pro Rekursionsstufe ein Teilwort angehängt wird und nach Rückkehr wieder entfernt. Das ist das "Gedächtnis" der Funktion, und wenn sie ein Wort der gewünschten Länge beisammen hat, kann sie den Pfad, auf dem sie dahin gekommen ist, auf diese Weise zusammenfassen.

Der erste Aufruf (Rekursionsstart) erfolgt für Position 0 und eine leere Teilwortkette. Die übrigen Parameter „beschreiben die Aufgabenstellung“, d.h. wie lang soll das Wort werden und wie sieht der Teilwort-Index aus. Der letzte Parameter sammelt die gefundenen Wortketten. Die Teilwortliste und die Wortketten sind Referenzparameter. Die Teilworte aus Performancegründen, PHP würde sonst wie jeck Arrays kopieren. Die Ergebnisliste muss per Referenz sein, sonst könnte PHP dort nichts speichern (Arrays werden als Kopie übergeben). Alternativ könnte man globale Variablen verwenden oder alles in ein Objekt packen.

Die rekursive Funktion sieht so aus: Zuerst prüft sie, ob sie fertig ist, und trägt das Ergebnis in die Ergebnisliste ein (Rekursionskern 1). Dann prüft sie, ob sie an einer Stelle angekommen ist von aus sie nicht weiter kann und bricht ab (Rekursionskern 2). Ansonsten probiert sie die Teilworte durch, die an dieser Stelle beginnen. Pro Teilwort hängt sie dieses Teilwort an die $partChain Liste (ok, das ist eigentlich ein Stack und keine Liste) und ruft sich dann selbst auf, mit der Fortsetzungsposition hinter dem gerade probierten Teilwort. Danach nimmt sie das Teilwort wieder weg.

function try_at_position($pos, &$partChain, $zielLänge, $index, &$chains)
{
   if ($pos == $zielLänge)
   {
	  $chains[] = implode("|", $partChain);
	  return;
   }
   if (!isset($index[$pos]))
      return;
	  
   foreach ($index[$pos] as $teil) 
   {
         array_push($partChain, $teil);
         try_at_position($pos+strlen($teil), $partChain, $zielLänge, $index, $chains);
         array_pop($partChain);
   }
}

Man kann das sicherlich auch mit einer Schleife statt mit einer Rekursion lösen, es sieht dann aber nicht mehr so elegant aus. In der Rekursion verwaltet sich das "Vor/Rück" beim Durchprobieren der Wortteile fast von allein - man braucht nur den $partChain-Stack um im Kern 1 den gefundenen Treffer zusammenzufassen.

Der meiste Programmcode (den man hier nicht sieht) geht eigentlich dafür drauf, die Referenzwortliste in den Suchindex zu übersetzen. Das sieht bei mir so aus - die Wortteile würde man wohl in einer praktischen Anwendung über eine SQL Query ermitteln und dann auch gleich die erste Position des Wortteils im Suchwort über SQL ermitteln lassen und nur die Folgepositionen in PHP.

$wortteile = [ "hotel", "hotelfach", "hotelfachfrau", "hot", "tel", "elf", "fach", "fachfrau", "ach", "chf", "frau", "fra", "rau" ];
$zielwort = "hotelfachfrau";

$index = build_index($zielwort, $wortteile);
if (!isset($index[0]))
{
   echo "Kein passender Wortanfang vorhanden";
   return;
}

function build_index($ziel, $teile) 
{
   $index = [];
   
   foreach ($teile as $teilNr => $teil)
   {
      $poslist = find_all_positions($ziel, $teil);
	  
      foreach ($poslist as $pos) 
      {
         if (!isset($index[$pos]))
            $index[$pos] = [];
         array_push($index[$pos], $teil);
      }
   }
   return $index;
}

function find_all_positions($wort, $teil) 
{
   $positionen = [];
   $start = 0;
   while (TRUE) 
   {
      $p = mb_stripos($wort, $teil, $start);
      if ($p === FALSE)
         return $positionen;
      array_push($positionen, $p);
      $start = $p+1;
   }
}

Rolf