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

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!);простое исправление предварительного вычисления длины даст yield (n · n!).Реализация требует Θ (n) памяти, которая является наилучшей из возможных, так как это размер ввода.

Answer 2

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

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

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