php - 如何返回给定字符串的所有组合？ (例如 'foo bar' = bar、bar_foo、foo)

Question

这个问题与上面建议的问题不重复。标题可能听起来相似，但它的答案不会以任何方式导致结果中描述的结果下面的问题。

---

我很难以递归方式遍历未知长度的数组来创建唯一的字符串组合。你能帮忙吗？

目标是获取像 foo bar 这样的字符串，并从该字符串创建独特的组合:

foo
bar
bar_foo (alphabetized to make unique combinations, not permutations)

另一个例子:

car bar add 应该返回:

add
add_bar
add_car
add_bar_car
bar
bar_car
car

这是我的进步:

function string_builder($length) {
    $arrWords = array('add','bar','car','dew','eat','fat','gym','hey','ink','jet','key','log','mad','nap','odd','pal','qat','ram','saw','tan','urn','vet','wed','xis','yap','zoo');
    $arr = array();
    for ($i=0; $i < $length; $i++) { 
        $arr[] = $arrWords[$i];
    }
    return implode(' ', $arr);
}
function get_combinations($string) {
    $combinations = array(); // put all combinations here
    $arr = explode(' ',$string);
    $arr = array_unique($arr); // only unique words are important
    sort($arr); // alphabetize to make unique combinations easier (not permutations)
    $arr = array_values($arr); // reset keys
    for ($i=0; $i < count($arr); $i++) {
        // this is where I'm stuck
        // how do I loop recursively through all possible combinations of an array?
    }
    return $combinations;
}
// Test it!
for ($i=1; $i < 26; $i++) { 
    $string = string_builder($i);
    $combinations = get_combinations($string);
    echo $i . " words\t" . count($combinations) . " combinations\t" . $string . "\n";
    // print_r($combinations);
}

---

另一个尝试:

function getCombinations2($str, $min_length = 2) {
    $words = explode(' ', $str);
    $combinations = array();
    $len = count($words);
    for ($a = $min_length; $a <= $min_length; $a++) {
        for ($pos = 0; $pos < $len; $pos ++) {
            if(($pos + $a -1) < $len) {
                $tmp = array_slice($words, $pos, $a);
                sort($tmp);
                $tmp = implode('_',$tmp);
                $combinations[] = $tmp;
            }
        }
    }
    $combinations = array_unique($combinations);
    return $combinations;
}

当您打印出这些组合并寻找一些应该存在的组合(例如，“fat_zoo”、“car_tan”)时，您就可以知道您已经成功了。我的两次尝试都会显示其中的几个，但不会显示全部。

Answer 1

您要搜索的内容很容易使用二进制数构建(并解释)。

二进制 word 中的每个位置都应指示是否附加了数组中的某个单词。

假设，您有一个由两个单词组成的数组:

$words = ["foo","bar"];

您现在期待组合

foo
bar
bar_foo

在二进制中这可以表示为

1 0
0 1
1 1

三个单词 $words = ["foo","bar", "baz"]; 就是组合

foo
bar
baz
foo_bar
foo_baz
bar_baz
foo_bar_baz

可以理解为

1 0 0
0 1 0
0 0 1
1 1 0
1 0 1
0 1 1 
1 1 1

(现在忽略字母排序)

让我们将这些二进制数按具体顺序移动并查看它们的十进制值:

0 0 1 // dec 1
0 1 0 // dec 2
0 1 1 // dec 3
1 0 0 // dec 4
1 0 1 // dec 5
1 1 0 // dec 6
1 1 1 // dec 7

注意:您要生成的元素数量是(2^n)-1，其中n 是您的字数。

这基本上就是您需要做的所有事情:

• 从 1 迭代到 (2^n)-1。
• 将该十进制数的二进制版本作为“数组索引”。
• 追加索引为“1”的元素。

PHP:

print_r(get_combinations("car bar add"));

function get_combinations($str) {
    $words = explode(' ',$str);
    $elements = pow(2, count($words))-1;

    $result = array();

    for ($i = 1; $i<=$elements; $i++){
        $bin = decbin($i);
        $padded_bin = str_pad($bin, count($words), "0", STR_PAD_LEFT);

        $res = array();
        for ($k=0; $k<count($words); $k++){
            //append element, if binary position says "1";
            if ($padded_bin[$k]==1){
                $res[] = $words[$k];
            }
        }

        sort($res);
        $result[] = implode("_", $res);
    }
    sort($result);
    return $result;
}

结果:

Array
(
    [0] => add
    [1] => bar
    [2] => bar_add
    [3] => car
    [4] => car_add
    [5] => car_bar
    [6] => car_bar_add
)

您可以在内爆之前按字母顺序对数组 $res 进行排序。

---

限于长度3:

print_r(get_combinations("car bar add"));

function get_combinations($str) {
    $words = explode(' ',$str);
    $elements = pow(2, count($words))-1;

    $result = array();

    for ($i = 1; $i<=$elements; $i++){
        $bin = decbin($i);
        $padded_bin = str_pad($bin, count($words), "0", STR_PAD_LEFT);

        $res = array();
        for ($k=0; $k<count($words); $k++){
           //break, if maximum length is reached.
           if (count($res) == 3){
             break;
           }           

           //append element, if binary position says "1";
            if ($padded_bin[$k]==1){
                $res[] = $words[$k];
            }
        }

        sort($res);

        //check result array if combination already exists before inserting.
        $res_string =implode("_", $res);
        if (!in_array($res_string, $result)){ 
          $result[] = $res_string;
        } 
    }
    sort($result);
    return $result;
}