Чтобы найти все возможные перестановки данной строки

Question

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

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

Я нашел решение в сети, которое использует рекурсию .. но это не удовлетворяет, так как выглядит немного ошибочным.

программа выглядит следующим образом: -

void permute(char s[], int d) 
{ 
    int i; 

    if(d == strlen(s)) 
     printf("%s",s); 

    else 
    { 
     for(i=d;i<strlen(s);i++) 
     { 
     swap(s[d],s[i]); 
     permute(s,d+1); 
     swap(s[d],s[i]); 
     } 
    } 
} 

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

Любой другой эффективный алгоритм, если существует, то, может также обсуждаться ....

И пожалуйста ,, это не HW ........

Спасибо .............

Answer 1

Код выглядит правильно, хотя у вас есть только ядро ​​алгоритма, а не полная программа. Вам нужно будет предоставить отсутствующие бит: заголовки, функцию main и макрос swap (вы можете сделать swap функцией, назвав ее swap(s, d, i)).

Чтобы понять алгоритм, было бы полезно добавить некоторый вывод трассировки, скажем printf("permute(%s, %d)", s, d) в начале функции permute, и запустить программу с 3- или 4-символьной строкой.

Основным принципом является то, что каждый рекурсивный вызов permute последовательно помещает каждый оставшийся элемент в положение d; элемент, который находился в позиции d, сохраняется путем помещения его туда, где был указан вышеупомянутый оставшийся элемент (т. е. элементы заменены). Для каждого размещения permute называется рекурсивно для генерации всех желаемых подстрок после позиции d. Таким образом, вызов верхнего уровня (d = 0) до permute последовательно пробует все элементы в позиции 0, вызовы второго уровня (d = 1) попробуйте все элементы в позиции 1, за исключением того, что уже находится в позиции 0 и т. Д. Следующий (d = n -1) есть один элемент, который нужно попробовать в последней позиции, а самые глубокие вызовы (d = n) распечатывают полученную перестановку.

Для основного алгоритма требуется время работы Θ (n · n!), Что является наилучшим возможным, поскольку это размер вывода. Однако эта реализация менее эффективна, потому что она перекомпонует strlen(s) на каждой итерации для времени работы Θ (n² · n!); простое исчисление предвычисления длины даст Θ (n · n!). Для реализации требуется Θ (n) память, что является наилучшим возможным, поскольку это размер ввода.

Answer 2

Для объяснения рекурсии см. Ответ Жиля.

У вашего кода есть некоторые проблемы. Сначала будет сложно реализовать требуемый swap как функцию на C, поскольку C не имеет понятия вызова по ссылке.Вы можете попытаться сделать это с помощью макроса, но тогда вам придется либо использовать эксклюзивную команду , либо, чтобы менять значения на месте или использовать временную переменную.

Затем ваше повторное использование strlen на каждом уровне рекурсии взорвает вашу сложность программы. Как вы это делаете, это делается на каждой итерации каждого уровня рекурсии. Поскольку ваша строка даже изменяется (из-за swap s), компилятор даже не сможет заметить, что это всегда одно и то же. Поэтому он ничего не сможет оптимизировать. Поиск завершающего '\0' в вашей строке будет доминировать над всеми другими инструкциями, если вы его реализуете так.