php - 在 PHP 中生成任意长度的有序(加权)组合

Question

给定一个常用词列表，按使用流行程度排序，是否有可能按照“最常见”序列的顺序形成任意长度的词组合(任何所需的词数)。例如，如果最常见的单词是“a、b、c”，那么对于长度为 2 的组合，将生成以下内容:

aa
ab
ba
bb
ac
bc
ca
cb
cc

这是长度为 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

这对于任意数量的元素的 2 或 3 个单词(设置长度)的组合实现起来很简单，但是对于任意长度可以做到这一点吗？我想在 PHP 中实现它，但非常感谢伪代码或算法摘要!

Answer 1

这可能是您需要的递归函数。这个想法是，当给定一个长度和一个字母时，首先生成所有短一个字母但不包含该字母的序列。将新字母添加到末尾，您就得到了涉及该字母的序列的第一部分。然后将新字母向左移动。循环遍历每个字母序列包括右边的新字母。

所以如果你有 gen(5, d)开始于

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

然后当它完成 a-c 组合时它会做

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

然后当它完成第 4 个字母 d 时，它将把它移到第 3 个

(aa)d(aa)

等等等等

<?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; 
} 

?>