php – 如何有效地生成给定长度字母的所有可能字母组合的数组？

发布时间：2020-12-13 16:53:52 所属栏目：PHP教程来源：网络整理

导读：想象一下,我有一袋26个拼字砖 – 英文字母中每个字母一个. 我的目标是创建一个包含最多n个字母的所有可能字符串的数组.说n = 3. 约束：字母必须始终按字母顺序排列(ABC,而不是CBA;组合,而不是排列) 字符串必须 = n个字母长(允许算法突破给定长度的任何循环)

想象一下,我有一袋26个拼字砖 – 英文字母中每个字母一个.

我的目标是创建一个包含最多n个字母的所有可能字符串的数组.说n = 3.

约束：

>字母必须始终按字母顺序排列(ABC,而不是CBA;组合,而不是排列)
>字符串必须< = n个字母长(允许算法突破给定长度的任何循环)
>信件不得重复(A,不是AA)

如何在PHP中最有效地生成此数组？

换句话说,如何避免暴力循环通过所有可能的组合并过滤掉那些与上述规则不匹配的组合？

如果我的字母只包含3个字母 – $alphabet = range(‘a’,’c’); – 我希望输出7个项目(3C1 3C2 3C3)：[A,B,C,AB,AC,BC,ABC].

如果我的字母只包含4个字母 – $alphabet = range(‘a’,’d’); – 我期望输出15个项目(4C1 4C2 4C3 4C4)：[A,D,AD,BD,CD,ABC,ABD,ACD,BCD,ABCD] .但是如果我想限制只有字符串< = 3个字母长,那么我会忽略ABCD,只产生14个项目(4C1 4C2 4C3).

$alphabet = range('a','z');

print_r(generate_strings($alphabet,1));
// expected output: A,...Z

print_r(generate_strings($alphabet,2));
// expected output: A..Z,AB..AZ,BC..BZ,..YZ

print_r(generate_strings($alphabet,3));
// expected output: A..Z,AB..YZ,ABC..XYZ

print_r(generate_strings($alphabet,10));
// expected output: A .. JKLMN .. AGKQRZ .. QRSTUVWXYZ
//                        ^         ^          ^10 character max,no repeats
//                        |         still alphabetical order
//                        alphabetical order

function generate_strings($alphabet,$max_word_length) {

    // how can I efficiently generate this array
    // without brute force looping through all of
    // the invalid and duplicate items like AA and CBA?

    return $array_of_all_possible_strings;
}

解决方法

我觉得这看起来很有趣.这是我的尝试,因为它值得：

function recurse($letters,&$words,$start,$end,$depth,$prefix = "") {
    $depth--;
    for ($i = $start; $i < $end; $i++) {
        $word = $prefix . $letters[$i];
        $words[] = $word;
        if ($depth) recurse($letters,$words,++$start,$word);
    }
}
function generate_strings($letters,$max_word_length) {
    $words = array();
    recurse($letters,count($letters),$max_word_length);
    return $words;      
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!