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

Question

Ist es möglich, aus einer Liste gebräuchlicher Wörter, die nach der Häufigkeit ihrer Verwendung geordnet sind, Wortkombinationen beliebiger Länge (beliebige Anzahl von Wörtern) in der Reihenfolge der "häufigsten" Sequenzen zu bilden? Wenn zum Beispiel die häufigsten Wörter "a, b, c" sind, dann würde für Kombinationen der Länge zwei das Folgende generiert werden:

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 (Satzlänge) 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äre sehr willkommen!

Answer 1

Hier ist eine rekursive Funktion, die Ihnen vielleicht weiterhilft. Die Idee ist, bei einer Länge und einem Buchstaben zunächst alle Sequenzen zu erzeugen, die einen Buchstaben kürzer sind und diesen Buchstaben nicht enthalten. Fügen Sie den neuen Buchstaben am Ende hinzu und Sie haben den ersten Teil der Folge, der diesen Buchstaben enthält. Verschieben Sie dann den neuen Buchstaben nach links. Durchlaufen Sie jede Buchstabenfolge einschließlich die neue rechts.

Wenn du also gen(5, d) hast Es würde beginnen mit

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

Wenn es dann mit den a-c-Kombinationen fertig ist, macht es

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

Wenn es dann mit d als 4. Buchstaben fertig ist, wird es auf den 3.

(aa)d(aa)

usw., 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; 
} 

?>

Answer 2

Ich habe nach php-Permutationen gegoogelt und bekam: http://www.php.happycodings.com/Algorithms/code21.html

Ich habe nicht nachgesehen, ob der Code gut ist oder nicht. Aber es scheint zu tun, was Sie wollen.

Answer 3

Ich weiß nicht, wie der Begriff für das lautet, was Sie zu berechnen versuchen, aber es handelt sich nicht um Kombinationen oder gar Permutationen, sondern um eine Art von Permutationen mit Wiederholungen.

Nachfolgend habe ich einen leicht angepassten Code aus dem nächstgelegenen Ding, das ich herumliegen habe, beigefügt, der etwas Ähnliches tut, einen String-Permutationsgenerator in LPC. Für a, b, c erzeugt er

abc
bac
bca
acb
cab
cba

Wahrscheinlich kann es so angepasst werden, dass das gewünschte Wiederholungsverhalten erreicht wird.

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, Ihr Problem zu formulieren, ist, dass Sie für eine Eingabe von N Elementen die Menge aller Pfade der Länge N in einem vollständig verbundenen, selbstverbundenen Graphen mit den Eingabeelementen als Knoten suchen.

Answer 4

Ich gehe davon aus, dass Sie, wenn Sie sagen, dass es bei fester Länge einfach ist, Folgendes meinen m verschachtelte Schleifen, wobei m ist die Länge der Sequenz (2 und 3 in Ihren Beispielen).

Sie könnten die Rekursion wie folgt verwenden:

Ihre Wörter sind mit 0, 1, n nummeriert, Sie müssen alle Folgen der Länge m :

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 kann dies umgesetzt werden? Nun, in jedem Aufruf können Sie ein weiteres Element an das Ende des Arrays schieben, und wenn Sie das Ende der Rekursion erreichen, drucken Sie den Inhalt des Arrays aus:

// 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 rufen Sie es wie folgt auf: generate(6, array())