Сгенерировать все возможные комбинации с помощью набора строк

В математической терминологии вы запрашиваете все возможные непустые упорядоченные подмножества входного набора. В онлайн-энциклопедии целочисленных последовательностей число таких последовательностей появляется как последовательность 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" } 

Вот моя реализация, которую я написал довольно долго, используя базовый математический определитель комбинации и перестановки. Может быть, это может помочь.

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

Вот моя наивная рекурсивная реализация:

 <?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' )); 

(Не знаю, что я сделал, конечно)

http://codepad.org/5OKhsCJg

Что вам нужно по массиву, по сути, является декартовым продуктом. Это аспект заданной математики и распространен в системах баз данных, а также на формальных языках моделирования. Будет ряд решений для реализации, если вы будете использовать этот термин для PHP.

(Я никогда не делал никакого PHP напрямую, поэтому я не хочу сообщать вам о некорректном (или взломанном) решении, но, надеюсь, это поможет привести вас к правильному пути)!