前言
我之前就在写类似的函数了，但是嵌套循环太复杂了，以至于放弃了，今天偶然发现了一个函数可以做到，就记录一下吧。
我正在尝试生成一组字符串的所有可能组合，每个字符串最多使用一次。
- 未定义输出字符串的长度（最大长度是给定字符串的数量，因为您只能使用它们一次）
- 例如，字符串集array('A','B')将生成A，B，AB，BA。
- 例如，字符串集array('ABC', 'Z')将生成'ABC'，'Z'，'ZABC'和'ABCZ'。
- 字符串集可以具有相同的条目，输出不需要是唯一的。例如，字符串集array('A', 'A')将生成'A'，'A'，'AA'，'AA'; （我实际上并不需要重复，但我不希望让事情变得更加困难）
我知道2个字符串有4个组合（2 =＆gt; 4）和3 =＆gt; 15,4 =＆gt; 64,5 =＆gt; 325 ...
由于我不是程序员，我发现它至少是“具有挑战性”。嵌套循环很快就太复杂了。更简单的解决方案是在字符串的索引中查找模式。但这让我重复使用字符串......
$strings = array('T','O','RS');
$num = 0;
$stringcount = count($strings);
$variations = array(0,1,4,15,64,325,1956,13699,109600,986409);
for($i=0;$i<$variations[$stringcount];$i++){
$index = base_convert($num, 10, $stringcount);
$array_of_indexes = str_split($index);
$out='';
for($j=0;$j<count($array_of_indexes);$j++){
$out .= $strings[$array_of_indexes[$j]];
}
echo $out . '<br />';
$num++;
}
结果： Ť Ø RS OT OO ORS RST RSO RSRS OTT OTO OTRS OOT OOO OORS
不好，不包括许多重复+许多有效组合
我知道这个解决方案在很多方面都是错误的，但我不知道从哪里开始？有什么建议？ Thx提前！
解决方法1
在数学术语中，您要求输入集的所有可能非空的有序子集。在整数序列的在线百科全书中，此类序列的数量显示为sequence A007526 - 请注意，此序列以4,15,64,325开头，与您发现的完全相同。
这个问题在Python中承认了一个非常简短，有效的解决方案，因此我将首先发布该解决方案：
def gen_nos(s):
for i in sorted(s):
yield i
s.remove(i)
for j in gen_nos(s):
yield i+j
s.add(i)示例：
list(gen_nos(set(['a', 'b', 'c'])))
['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']
请注意，sorted并非绝对必要;它只是确保输出按字典顺序排序（否则，元素按设定顺序迭代，这基本上是任意的）。
要将其转换为PHP，我们必须使用带有额外数组参数的递归函数来保存结果：
function gen_nos(&$set, &$results) {
for($i=0; $i<count($set); $i++) {
$results[] = $set[$i];
$tempset = $set;
array_splice($tempset, $i, 1);
$tempresults = array();
gen_nos($tempset, $tempresults);
foreach($tempresults as $res) {
$results[] = $set[$i] . $res;
}
}
}
示例：
$results = array();
$set = array("a", "b", "c");
gen_nos($set, $results);
var_dump($results);
产生：
array(15) {
[0]=>
string(1) "a"
[1]=>
string(2) "ab"
[2]=>
string(3) "abc"
[3]=>
string(2) "ac"
[4]=>
string(3) "acb"
[5]=>
string(1) "b"
[6]=>
string(2) "ba"
[7]=>
string(3) "bac"
[8]=>
string(2) "bc"
[9]=>
string(3) "bca"
[10]=>
string(1) "c"
[11]=>
string(2) "ca"
[12]=>
string(3) "cab"
[13]=>
string(2) "cb"
[14]=>
string(3) "cba"
}
解决方法2
这是我使用组合和置换的基本数学定义写了很长时间的实现。也许这可能有所帮助。
<?php
/**
* Generate all the combinations of $num elements in the given array
*
* @param array $array Given array
* @param int $num Number of elements ot chossen
* @param int $start Starter of the iteration
* @return array Result array
*/
function combine($array, $num, $start = 0) {
static $level = 1;
static $result = array();
$cnt = count($array);
$results = array();
for($i = $start;$i < $cnt;$i++) {
if($level < $num ) {
$result[] = $array[$i];
$start++;
$level++;
$results = array_merge($results, combine($array, $num, $start));
$level--;
array_pop($result);
}
else {
$result[] = $array[$i];
$results[] = $result;
array_pop($result);
}
}
return $results;
}
/**
* Generate all the permutations of the elements in the given array
*/
function permute($array) {
$results = array();
$cnt = count($array);
for($i=0;$i<$cnt;$i++) {
$first = array_shift($array);
if(count($array) > 2 ) {
$tmp = permute($array);
}
elseif(count($array) == 2) {
$array_ = $array;
krsort($array_);
$tmp = array($array, $array_);
}
elseif(count($array) == 1) {
$tmp = array($array);
}
elseif(count($array) == 0) {
$tmp = array(array());
}
foreach($tmp as $k => $t) {
array_unshift($t, $first);
$tmp[$k] = $t;
}
$results = array_merge($results, $tmp);
array_push($array, $first);
}
return $results;
}
$strings = array('T', 'O', 'RS');
$strings_count = count($strings);
$combinations = array();
for ($i = 1; $i <= $strings_count; $i++) {
$combination = combine($strings, $i, 0);
$combinations = array_merge($combinations, $combination);
}
$permutations = array();
foreach($combinations as $combination) {
$permutation = permute($combination);
$permutations = array_merge($permutations, $permutation);
}
print_r($combinations);
print_r($permutations);
解决方法3
这是我天真的递归实现：
<?php
// Lists all ways to choose X from an array
function choose($x, array $arr) {
$ret = array();
if ($x === 0) {
// I don't think this will come up.
return array();
} else if ($x === 1) {
foreach ($arr as $val) {
$ret[] = array($val);
}
} else {
$already_chosen = choose($x - 1, $arr);
for ($i = 0, $size_i = sizeof($arr); $i < $size_i; $i++) {
for ($j = 0, $size_j = sizeof($already_chosen); $j < $size_j; $j++) {
if (!in_array($arr[$i], $already_chosen[$j])) {
$ret[] = array_merge(
array($arr[$i]),
$already_chosen[$j]
);
}
}
}
}
return $ret;
}
function choose_all($arr) {
for ($i = 1, $size = sizeof($arr); $i <= $size; $i++) {
foreach (choose($i, $arr) as $val) {
echo implode(":", $val).PHP_EOL;
}
}
}
choose_all(array(
"A",
"B",
));
echo "--".PHP_EOL;
choose_all(array(
"ABC",
"Z",
));
echo "--".PHP_EOL;
choose_all(array(
'T',
'O',
'RS'
));
