Php Array Permutation nach festen Muster
Simone
Php Array Permutation nach festen Muster
Simone
Rolf BHallo,
Komme nicht so richtig weiter... Vielleicht könnt Ihr mal rüber schauen ;o)
Zum Problem: ich habe einen Array mit variabler Größe wo einzelne Worte in bestimmten Kombinationen ein festgelegtes Ausgangswort ergeben sollen.
Ausgangswort: hotelfachfrau
Array
hotel
hotelfach
hotelfachfrau
hot
elf
fach
fachfrau
ach
frau
rau
Übereinstimmungen : a.) hotelfachfrau, b.) hotel|fach|frau c.) hotelfach|frau
Und jetzt mein Quelltext:
<?php
/*
Ausgangswort:
hotelfachfrau
Array
hotel
hotelfach
hotelfachfrau
hot
elf
fach
fachfrau
ach
frau
rau
*/
$json ='{"0":["hotel","hotelfach","hotelfachfrau","hot"],"2":["tel"],"3":["elf"],"5":["fach","fachfrau","fac"],"6":["ach"],"7":["chf"],"9":["frau","fra"],"10":["rau"]}';
$json_array = json_decode($json,true);
/*
Array
(
[0] => Array
(
[0] => hotel
[1] => hotelfach
[2] => hotelfachfrau
[3] => hot
)
[2] => Array
(
[0] => tel
)
[3] => Array
(
[0] => elf
)
[5] => Array
(
[0] => fach
[1] => fachfrau
[2] => fac
)
[6] => Array
(
[0] => ach
)
[7] => Array
(
[0] => chf
)
[9] => Array
(
[0] => frau
[1] => fra
)
[10] => Array
(
[0] => rau
)
)
*/
echo "<pre>";
echo "<h3>Ausgangswort : hotelfachfrau</h3>";
print_r($json_array);
echo "<br>";
echo "Übereinstimmungen : a.) hotelfachfrau, b.) hotel|fach|frau c.) hotelfach|frau <br>";
$ausgangswort = 'hotelfachfrau';
$strlen_ausgangswort = mb_strlen($ausgangswort);
foreach($json_array[0] as $key => $teil_str)
{
$strlen_teil_str = mb_strlen($teil_str);
if(!empty($json_array[$strlen_teil_str]))
{
echo '<b>'.$teil_str.'</b><br>';
foreach($json_array[$strlen_teil_str] as $wort_teilstring)
{
echo $teil_str.'|'.$wort_teilstring.'<br>';
}
}
}
echo "</pre>";
?>
Es fehlt die Permutation (Funktion) in der zweiten Schleife...
Danke!
-
Hey,
Zum Problem: ich habe einen Array mit variabler Größe wo einzelne Worte in bestimmten Kombinationen ein festgelegtes Ausgangswort ergeben sollen.
Wie wäre es wenn du jeden String in dem Array prüfst ob dieser in dem Ausgangswort vorhanden ist.
$a = "String1"; $b = "ring" $c = strpos($a, $b); // position falls $b in $a: hier $c = 2 // false falls $b nicht in $aDanach könntest du prüfen welche Teilstrings zusammen das Ausgangswort ergeben. Indem du zum Beispiel alle Teilstring nach ihrer Position ordnest auf die Position könntest du die länge addieren und einen Teilstring suchen der an dem Ergebnis anfängt.
Es fehlt die Permutation (Funktion) in der zweiten Schleife...
Ich bin mir hier nicht ganz sicher ob du "Permutation" falsch benutzt. Eine Permutation ist eine Möglichkeit eine Abfolge zu Ordnen.
Gruß
Jo-
Hi,
vielen Dank für Deine Antwort!
Alle Worte im Array sind im ausgangswort = 'hotelfachfrau' enthalten. Der Key des Arrays entspricht der Position der Fundstelle im Ausgangswort.
Ich bin jetzt soweit das ich die Permutation fertig habe ;o)
Array ( [0] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fach [6] => ach [7] => chf [9] => frau [10] => rau ) [1] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fach [6] => ach [7] => chf [9] => fra [10] => rau ) [2] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fachfrau [6] => ach [7] => chf [9] => frau [10] => rau ) [3] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fachfrau [6] => ach [7] => chf [9] => fra [10] => rau ) [4] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fac [6] => ach [7] => chf [9] => frau [10] => rau ) [5] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fac [6] => ach [7] => chf [9] => fra [10] => rau ) [6] => Array ( [0] => hotelfach [2] => tel [3] => elf [5] => fach [6] => ach [7] => chf [9] => frau [10] => rau ) [7] => Array ( [0] => hotelfach [2] => tel [3] => elf [5] => fach [6] => ach [7] => chf [9] => fra [10] => rau ) [8] => Array ( [0] => hotelfach [2] => tel [3] => elf [5] => fachfrau [6] => ach [7] => chf [9] => frau [10] => rau ) usw.Danke nochmal
-
Hey,
Ich bin jetzt soweit das ich die Permutation fertig habe ;o)
Wie schon vermutet benutzt du das Wort Permutation falsch.
Array[0]hat alleine schon 10! Permutationen, das sind 3.628.800 unterschiedliche Positionen der Werte in dem Array.Nachtrag: Was mir gerade auffällt, die sind ja alle gleich? Das hat nun garnichts mit Permutation zutun. Einen Permutationsalgorithmus könntest du zum Beispiel in 4 einfachen Schritten programmieren.
Array ( [0] => Array ( [0] => hotel [2] => tel [3] => elf [5] => fach [6] => ach [7] => chf [9] => frau [10] => rau ))Aber gut, nehme wir nun dieses. Auf die Position also den Key kannst du jetzt die Länge des Strings addieren. Für
[2] = "tel"wäre das $$2+3=5$$ damit weißt du das nurarray[5]aufarray[2]folgen kann. $$5+4=9$$ damit wäre der letzte Werarray[9]. Problem ist jetzt das dir in der Kette die 0 fehlt, was passiert damit?Gruß
Jo-
Hi, Danke für Deine Gedanken.
Ich habe es jetzt so umgesetzt.
echo "<pre>"; $ausgangswort = 'hotelfachfrau'; $strlen_ausgangswort = mb_strlen($ausgangswort); $data =' [{"0":"hotel","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotel","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotel","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotel","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotel","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotel","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfach","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hotelfachfrau","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fach","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fachfrau","6":"ach","7":"chf","9":"fra","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"frau","10":"rau"},{"0":"hot","2":"tel","3":"elf","5":"fac","6":"ach","7":"chf","9":"fra","10":"rau"}]'; $json_array = json_decode($data,true); $array_kombi = array(); foreach($json_array as $teil_str_array) { $teil_str_val = $teil_str_array[0]; $strlen_teil_str_wort = $strlen_teil_str = mb_strlen($teil_str_val); $temp_w_z= $temp_w = $teil_str_val; foreach($teil_str_array as $key => $teil_str_wort) { if($key === 0) { continue; } if($key < $strlen_teil_str) { continue; } if($key >= $strlen_teil_str_wort) { $temp_w = $temp_w.$teil_str_wort; $strlen_teil_str_wort = mb_strlen($temp_w); $temp_w_z = trim($temp_w_z.'|'.$teil_str_wort); if($strlen_ausgangswort === $strlen_teil_str_wort) { if (!in_array($temp_w_z, $array_kombi)) { $array_kombi[] = $temp_w_z; echo $temp_w_z.'<br>'; } } } } } print_r($json_array); print_r($array_kombi); echo "</pre>";-
Hallo Simone,
könntest Du mal die EIGENTLICHE Aufgabe beschreiben? Was bekommst Du, was sollst Du damit tun? Es kommt mir nämlich merkwürdig vor, dass Du in deiner "Lösung" dieses monströse $data Dings aufbaust. Es sieht irgendwie so aus, als wäre das keine Lösung, sondern eine von Hand vorbereitete Umsetzung einer eigentlich anders gearteten Aufgabe.
Lautet die Aufgabe vielleicht: Schreibe eine Funktion, die aus einer Liste von Wortfragmenten alle Möglichkeiten ermittelt, daraus ein bestimmtes Zielwort zusammenzusetzen? Und die Hotelfachfrau war nur ein Beispiel?
Was wäre mit dieser Ausgangsbasis:
$wortteile = [ "hotel","hotelfach","hotelfachfrau", "hot", "tel", "elf", "fach","fachfrau","fac", "h", "o", "t", "e", "l", "ach", "chf", "frau","fra", "rau" ]; $zielwort = "hotelfachfrau"; $ketten = hier_geschieht_ein_wunder($wortteile, $zielwort); var_dump($ketten);Da sollte dann folgendes rauskommen:
array(14) { [0]=> string(15) "hotel|fach|frau" [1]=> string(14) "hotel|fachfrau" [2]=> string(16) "hotel|fac|h|frau" [3]=> string(14) "hotelfach|frau" [4]=> string(13) "hotelfachfrau" [5]=> string(16) "hot|elf|ach|frau" [6]=> string(17) "hot|e|l|fach|frau" [7]=> string(16) "hot|e|l|fachfrau" [8]=> string(18) "hot|e|l|fac|h|frau" [9]=> string(17) "h|o|tel|fach|frau" [10]=> string(16) "h|o|tel|fachfrau" [11]=> string(18) "h|o|t|elf|ach|frau" [12]=> string(19) "h|o|t|e|l|fach|frau" [13]=> string(18) "h|o|t|e|l|fachfrau" }Rolf
--
sumpsi - posui - clusi-
Hallo Rolf,
@Aufgabe Es soll ein Funktion erstellt werden die "ein unbekanntes Worte" in "bekannte Worte" zerlegt. Ein Abgleich des unbekannten Wort mit einer Referenzdatenbank stellt eine Liste von Worte bereit die im Array mit Anfangsposition des erkannten Wortes abgebildet werden.
hotel hotelfach hotelfachfrau hot elf fach fachfrau ach frau rauAus den mit Referenzen abgelegten Wörtern ergeben sich für:
hotelfachfrau
somit folgende Kombinationen:
Array ( [0] => hotelfach|frau [1] => hotel|fachfrau [2] => hotel|fach|frau [3] => hot|elf|ach|frau )@Lautet die Aufgabe vielleicht: Schreibe eine Funktion, die aus einer Liste von Wortfragmenten alle Möglichkeiten ermittelt, daraus ein bestimmtes Zielwort zusammenzusetzen?
Genau dort bin ich nicht weitergekommen!
den Array mit seinen Elementen so zu durchlaufen das sich das Wort "hotelfachfrau" ergibt. ohne Permutation wie jetzt gelöst- ist ja eigentlich nicht notwendig...
Danke für Dein Feedback
-
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
--
sumpsi - posui - clusi-
Hallo Rolf,
ich bedanke mich für Deine Magie!
werde mich Zeile für Zeile durch Deinen Quelltext arbeiten.
In der Tat habe ich auf eine Permutation zurückgegriffen.
function permu(array $array, $inb=false) { switch (count($array)) { case 1: return $array[0]; break; case 0: break; } $keys = array_keys($array); #print_r($keys); $a = array_shift($array); $k = array_shift($keys); #print_r($a); $b = permu($array, 'recursing'); $return = array(); foreach ($a as $v) { if($v) { foreach ($b as $v2) { $v2 = is_array($v2) ? $v2 : array($v2); if($inb == 'recursing') $return[] = array_merge(array($v), (array) $v2); else $return[] = array($k => $v) + array_combine($keys, $v2); } } } return $return; } -
Hi Rolf,
Danke nochmal für Deine Funktion!
Eine kleine Ergänzung noch für die Nachwelt:
Hier die Fassung für Umlaute und Co.:
alt: try_at_position($pos+strlen($teil), $partChain, $zielLänge, $index, $chains);
neu: try_at_position($pos+mb_strlen($teil), $partChain, $zielLänge, $index, $chains);
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+mb_strlen($teil), $partChain, $zielLänge, $index, $chains); array_pop($partChain); } }-
Hallo Simone,
ja, sorry. Das mb_ vergesse ich gerne mal. In find_all_positions hatte ich noch daran gedacht :)
Rolf
--
sumpsi - posui - clusi
-
-
-
-
Hi Rolf,
@hier_geschieht_ein_wunder ;o)
... jetzt muss ich lachen …
Ich möchte das Wunder sehen, selber erleben!
Danke
-
-
-
-
-