这个问题不是上面建议的问题的重复。标题听起来可能与相似，但它的答案无论如何都不会导致下面问题所描述的结果。
我有一个困难的时间递归迭代通过未知长度的数组来创建字符串的唯一组合。你能帮忙吗?
目标是获取一个像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")时，您可以知道您成功了。我的两个尝试都将显示其中的几个，但不会显示全部。
您正在搜索的内容很容易使用二进制数构建(并解释)。
二进制字中的每个位置应指示是否追加了数组中的某个字。
让我们假设，你有一个由两个单词组成的数组:
$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"的元素
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;
}
如果您使用的是PHP 5.5，您可以使用生成器来消除内存问题。它还降低了总体执行时间。
Generators
15: 256kb, 0.48s
16: 256kb, 0.90s
19: 256kb, 7.76s
Original
15: 5.75mb, 0.49s
16: 17.25mb, 0.99s
19: 86.24mb, 8.58s
基于dognose的函数，你可以将$result[]赋值替换为$res。该函数不是遍历整个循环并返回一个巨大的数组，而是逐个遍历，每次返回(产生)一个元素。
function combo_gen($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);
$res = implode("_", $res);
yield $res;
}
}
foreach(combo_gen('one two three') as $item) {
//stuff
}}
可能有一个更优雅的解决方案，但是我使用了两个函数。
getCombosOfLength函数给出数组中的每个$intLength组合。GetCombos函数只是对你想要的每个长度运行GetCombosOfLength。这对于生成1-5个项目的所有组合非常有效。如果你对所有25个项目的组合运行它，它会有一些问题。
$a = array("c", "b", "f", "v", "g", "e", "h", "i", "j", "k", "l", "m", "n", "p", "o", "r", "a", "q", "s", "t", "u", "w", "x", "y", "z");
$b = getCombos($a, 5);
print "<pre>'n";
print_r($b);
function getCombos($arrInput, $intMax = null) {
sort($arrInput);
if (is_null($intMax)) $intMax = count($arrInput);
$arrOutput = array();
for ($i = $intMax; $i > 0; $i--) {
$arrReturn = getCombosOfLength($arrInput, $i);
for ($j = 0; $j < count($arrReturn); $j++) $arrOutput[] = $arrReturn[$j];
}
return $arrOutput;
}
function getCombosOfLength($arrInput, $intLength) {
$arrOutput = array();
if ($intLength == 1) {
for ($i = 0; $i < count($arrInput); $i++) $arrOutput[] = array($arrInput[$i]);
return $arrOutput;
}
$arrShift = $arrInput;
while (count($arrShift)) {
$x = array_shift($arrShift);
$arrReturn = getCombosOfLength($arrShift, $intLength - 1);
for ($i = 0; $i < count($arrReturn); $i++) {
array_unshift($arrReturn[$i], $x);
$arrOutput[] = $arrReturn[$i];
}
}
return $arrOutput;
}