Generieren geordneter (gewichteter) Kombinationen beliebiger Länge in PHP

Question

Angesichts einer Liste von gebräuchlichen Wörtern, sortiert in der Reihenfolge der Häufigkeit der Verwendung, ist es möglich, Wortkombinationen beliebiger Länge (beliebig viele Wörter) in der Reihenfolge von zu bilden die "häufigsten" Sequenzen. Wenn beispielsweise die am häufigsten verwendeten Worte ‚a, b, c‘ dann für Kombinationen von Länge zwei sind, würden die folgenden generiert:

aa 
ab 
ba 
bb 
ac 
bc 
ca 
cb 
cc 

Hier ist die richtige Liste für Länge 3:

aaa 
aab 
aba 
abb 
baa 
bab 
bba 
bbb 
aac 
abc 
bac 
bbc 
aca 
acb 
bca 
bcb 
acc 
bcc 
caa 
cab 
cba 
cbb 
cac 
cbc 
cca 
ccb 
ccc 

Dies ist einfach zu implementieren für Kombinationen von 2 oder 3 Wörtern (Länge einstellen) für eine beliebige Anzahl von Elementen, aber kann dies für beliebige Längen getan werden? Ich möchte dies in PHP implementieren, aber Pseudocode oder sogar eine Zusammenfassung des Algorithmus würde sehr geschätzt werden!

Answer 1

Ich googeln für PHP-Permutationen und bekam: http://www.php.happycodings.com/Algorithms/code21.html

ich nicht in den Code ausgesehen haben, ob es gut ist oder nicht. Aber es scheint zu tun, was du willst.

Answer 2

Ich weiß nicht, was der Begriff für das ist, was Sie zu berechnen versuchen, aber es ist nicht Kombinationen oder sogar Permutationen, es ist eine Art von Permutationen-mit-Wiederholung.

Im Folgenden habe ich etwas leicht angepassten Code von der nächsten Sache, die ich herumliegen habe, die so etwas wie einen String Permutation Generator in LPC beigefügt. Für a, b, c erzeugt sie

abc 
bac 
bca 
acb 
cab 
cba 

Wahrscheinlich kann es die Wiederholung Verhalten, das Sie aktivieren möchten gezwickt werden.

varargs mixed array permutations(mixed array list, int num) { 
    mixed array out = ({}); 
    foreach(mixed item : permutations(list[1..], num - 1)) 
     for(int i = 0, int j = sizeof(item); i <= j; i++) 
      out += ({ implode(item[0 .. i - 1] + ({ list[0] }) + item[i..], "") }); 
    if(num < sizeof(list)) 
     out += permutations(list[1..], num); 
    return out; 
} 

FWIW, eine andere Art und Weise Ihr Problem auszudrücken, besteht darin, dass für eine Eingabe von N Elementen, können Sie die Menge aller Pfade der Länge N wollen in einem vollständig angeschlossen, selbst verbunden Graph mit den Eingabeelementen wie Knoten.

Answer 3

Ich gehe davon aus, dass, wenn es einfach ist für feste Länge zu sagen, sie ist m verschachtelte Schleifen verwenden, wo m die Länge der Sequenz ist (2 und 3 in Ihren Beispielen).

Sie könnten Rekursion wie folgt verwenden:

Ihre Worte sind nummeriert 0, 1, .. n, müssen Sie alle Sequenzen der Länge m generieren:

generate all sequences of length m: 
{ 
    start with 0, and generate all sequences of length m-1 
    start with 1, and generate all sequences of length m-1 
    ... 
    start with n, and generate all sequences of length m-1 
} 

generate all sequences of length 0 
{ 
    // nothing to do 
} 

Wie dies implementieren ? Nun, in jedem Aufruf können Sie ein weiteres Element drücken, um das Ende des Arrays, und wenn Sie das Ende der Rekursion getroffen, ausdrucken Array Inhalt:

// m is remaining length of sequence, elements is array with numbers so far 
generate(m, elements) 
{ 
    if (m == 0) 
    { 
     for j = 0 to elements.length print(words[j]); 
    } 
    else 
    { 
     for i = 0 to n - 1 
     { 
      generate(m-1, elements.push(i)); 
     } 
    } 
} 

Und schließlich nennen es wie folgt aus: erzeugen (6, array())

Answer 4

Hier ist eine rekursive Funktion, die möglicherweise das ist, was Sie brauchen. Die Idee ist, bei Angabe einer Länge und eines Buchstabens zuerst alle Sequenzen zu erzeugen, die einen Buchstaben kürzer sind und diesen Buchstaben nicht enthalten. Fügen Sie den neuen Buchstaben an das Ende und Sie haben den ersten Teil der Sequenz, die diesen Brief enthält. Dann bewege den neuen Buchstaben nach links. Durchlaufen Sie jede Buchstabenfolge einschließlich die neue auf der rechten Seite.

Also, wenn Sie gen hatte (5, d) Es würde beginnen mit

(aaaa)d 
(aaab)d 
... 
(cccc)d 

dann, wenn es mit den AC-Kombinationen hinbekommen würde es dann

(aaa)d(a) 
... 
(aaa)d(d) 
(aab)d(d) 
... 
(ccc)d(d) 

tun, wenn es hinbekommen mit d als 4. Schreiben ist es in den 3.

(aa)d(aa) 

usw. bewegen, usw.

<?php 
/** 
* Word Combinations (version c) 6/22/2009 1:20:14 PM 
* 
* Based on pseudocode in answer provided by Erika: 
* http://stackoverflow.com/questions/1024471/generating-ordered-weighted-combinations-of-arbitrary-length-in-php/1028356#1028356 
* (direct link to Erika's answer) 
* 
* To see the results of this script, run it: 
* http://stage.dustinfineout.com/stackoverflow/20090622/word_combinations_c.php 
**/ 

init_generator(); 

function init_generator() { 
    global $words; 
    $words = array('a','b','c'); 
    generate_all(5); 


} 

function generate_all($len){ 
    global $words; 
    for($i = 0; $i < count($words); $i++){ 
     $res = generate($len, $i); 

     echo join("<br />", $res); 
     echo("<br/>"); 
    } 
} 

function generate($len, $max_index = -1){ 
    global $words; 

    // WHEN max_index IS NEGATIVE, STARTING POSITION 
    if ($max_index < 0) { 
     $max_index = count($words) - 1; 
    } 

    $list = array(); 


    if ($len <= 0) { 
     $list[] = ""; 
     return $list; 
    } 

    if ($len == 1) { 

     if ($max_index >= 1) { 
      $add = generate(1, ($max_index - 1)); 
      foreach ($add as $addit) { 
       $list[] = $addit; 
      } 


     } 
     $list[] = $words[$max_index]; 
     return $list; 
    } 

    if($max_index == 0) { 
     $list[] = str_repeat($words[$max_index], $len); 
     return $list; 
    } 

    for ($i = 1; $i <= $len; $i++){ 
     $prefixes = generate(($len - $i), ($max_index - 1)); 
     $postfixes = generate(($i - 1), $max_index); 
     foreach ($prefixes as $pre){ 
      //print "prefix = $pre<br/>"; 
      foreach ($postfixes as $post){ 
       //print "postfix = $post<br/>"; 
       $list[] = ($pre . $words[$max_index] . $post); 
      } 
     } 
    } 
    return $list; 
} 

?>