Мне нужен алгоритм, которые возвращают всю возможную комбинацию всех символов в одной строке.
Я попробовал:
$langd = strlen($input);
for($i = 0;$i < $langd; $i++){
$tempStrang = NULL;
$tempStrang .= substr($input, $i, 1);
for($j = $i+1, $k=0; $k < $langd; $k++, $j++){
if($j > $langd) $j = 0;
$tempStrang .= substr($input, $j, 1);
}
$myarray[] = $tempStrang;
}
Но это только возвращает ту же комбинацию суммы как длина строки.
Скажите $input = "hey"
, результат был бы: hey, hye, eyh, ehy, yhe, yeh
.
Я бы поместил все символы в массив и написал рекурсивную функцию, которая будет "вычеркивать" все оставшиеся символы. Если массив пуст, то в переданный по ссылке массив.
<?php
$input = "hey";
function string_getpermutations($prefix, $characters, &$permutations)
{
if (count($characters) == 1)
$permutations[] = $prefix . array_pop($characters);
else
{
for ($i = 0; $i < count($characters); $i++)
{
$tmp = $characters;
unset($tmp[$i]);
string_getpermutations($prefix . $characters[$i], array_values($tmp), $permutations);
}
}
}
$characters = array();
for ($i = 0; $i < strlen($input); $i++)
$characters[] = $input[$i];
$permutations = array();
print_r($characters);
string_getpermutations("", $characters, $permutations);
print_r($permutations);
Выводит:
Array
(
[0] => h
[1] => e
[2] => y
)
Array
(
[0] => hey
[1] => hye
[2] => ehy
[3] => eyh
[4] => yhe
[5] => yeh
)
Ах да, комбинации = порядок не имеет значения. Перестановки = порядок имеет значение.
Итак, hey, hye yeh - все это одна и та же комбинация, но 3 отдельные перестановки, как уже говорилось. Следите за тем, чтобы шкала элементов увеличивалась очень быстро. Это называется факториал, и записывается как 6! = 6*5*4*3*2*1 = 720 элементов (для строки из 6 символов). Для строки из 10 символов будет уже 10! = 3628800 перестановок, что является очень большим массивом. В данном примере это 3! = 3*2*1 = 6.
Вы можете использовать подход, основанный на обратном отслеживании, чтобы систематически генерировать все перестановки:
// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str,$i,$n) {
if ($i == $n)
print "$str\n";
else {
for ($j = $i; $j < $n; $j++) {
swap($str,$i,$j);
permute($str, $i+1, $n);
swap($str,$i,$j); // backtrack.
}
}
}
// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
$temp = $str[$i];
$str[$i] = $str[$j];
$str[$j] = $temp;
}
$str = "hey";
permute($str,0,strlen($str)); // call the function.
Выход:
#php a.php
hey
hye
ehy
eyh
yeh
yhe