Как создать перестановку строки (длиной 10 и более символов)? - PullRequest
Новая
       5

Как создать перестановку строки (длиной 10 и более символов)?

0 голосов
/ 11 февраля 2012

У меня есть задание, которое делает меня немного сумасшедшим, есть раздел, посвященный перестановкам слов, после того, как я просмотрел Интернет, я нашел функцию для выполнения перестановок, как показано ниже:чтобы показать результат: 

print_r(array_unique(permute("abcdefghi"))); // found 362880
print_r(array_unique(permute("abcdefghij"))); // error

Проблема в том, что эта функция способна выполнять только все перестановки из 9 символов (приблизительно 362880 комбинаций, с длительным временем и заставить браузер не отвечать на крошечное время).При попытке выполнить перестановку длиной до 10 символов появится сообщение об ошибке:

Неустранимая ошибка: допустимый объем памяти 134217728 байт исчерпан (попытка выделить 35 байт)

У вас есть решение или другой способ сделать перестановки длиной 10 символов или более?

1 Ответ

3 голосов
/ 11 февраля 2012

Количество перестановок строки длиной N равно N!

Так что, если вы просто ищете количество перестановок, это будет делать: 

function factorial($n) {
    if( $n == 0) return 1;
    if( $n < 3) return $n;
    return $n*factorial($n-1);
}
function permute($str) {
    return factorial(strlen($str));
}

Если, однако, вы пытаетесь получить случайную одну из этих перестановок, попробуйте это: 

function permute($str) {
    $l = strlen($str);
    $a = str_split($str);
    $ret = "";
    while($l > 0) {
        $i = rand(0,$l-1);
        $ret .= $a[$i];
        array_splice($a,$i,1);
        $l--;
    }
    return $ret;
}

Если вы пытаетесь перебрать все N! перестановки, попробуйте: 

ini_set("memory_limit",-1);
set_time_limit(0);
// your brute-force code here

Если ни один из них не ответит на ваш вопрос, уточните;)

...