Все возможные перестановки букв слова - нужен алгоритм

@dimcoder · Регистрация: 11.09.2011

Author24 — интернет-сервис помощи студентам

Доброго времени суток, форумчане. Помогите пожалуйста найти/составить алгоритм решения следующей задачи:
Дано слово. Найти все возможные варианты перестановки его букв.

Пример:
Дано:
abc
Вывести:
acb
abc
bac
bca
cba
cab

PS Встречал я кое-где решение с next_permutation, но мне важно решить без всяких левых функций.

PSS Ну и программу по ходу дела смастерить тоже нужно

go · 03.12.2011, 20:35

Сообщение от dimcoder

Гуууугл?

http://rain.ifmo.ru/cat/view.p... tions-2000

Добавлено через 1 минуту
Можно еще с помощью рекурсии

@dimcoder · 04.12.2011, 09:17 **[ТС]**

Сообщение от go

http://rain.ifmo.ru/cat/view.php/vis...mutations-2000

Спасибо за ссылку, полезно.

Сообщение от go

Можно еще с помощью рекурсии

Предпочитаю, как то без этих рекурсий делать. Они память грузят. Говорят, мол, красиво через рекурсию - для меня пока запутанно больше. Да и потом, любую задачу, которую можно решить рекурсивно, можно решить и через цикл. Но всё же со временем я напишу рекурсивный код.

Байт · 04.12.2011, 09:58

Вот такой есть НЕРЕКУРСИВНЫЙ алгоритм

C

#include <stdio.h>
#define N 6
 
main()
{ char s[N+1], t; int i, j, r, k;
 
 for(i=0; i<N; i++) s[i] = '1'+i;
 s[N] = '\0';
 
 while(1) {
   printf("%s\n", s);
       // Находим самое правое место, где s[i] < s[i+1]
   for(i=N-1; i>=0 && s[i] > s[i+1]; i--) ;
   if (i<0) break; // Уже получили "654321" - самую старшую перестановку
       // Находим s[j] - наименьший элемент справа от s[i] и больший его
   for(j=N-1; s[i] > s[j]; j--) ;
       // Меняем s[i] <-> s[j]
   t = s[j];
   s[j] = s[i];
   s[i] = t;
       // То, что за "i" - переворачиваем
   for(k=i+1, r=N-1; r > k; k++, r--) {
     t = s[r];
     s[r] = s[k];
     s[k] = t;
   }
 }
}
/*****************/

Нашел в книге Липского "Комбинаторика для программистов"

@dimcoder Полярный 476 / 448 / 158 Регистрация: 11.09.2011 Сообщений: 1,156
	04.12.2011, 09:17 [ТС]	22
	Сообщение от go http://rain.ifmo.ru/cat/view.php/vis...mutations-2000 Спасибо за ссылку, полезно. Сообщение от go Можно еще с помощью рекурсии Предпочитаю, как то без этих рекурсий делать. Они память грузят. Говорят, мол, красиво через рекурсию - для меня пока запутанно больше. Да и потом, любую задачу, которую можно решить рекурсивно, можно решить и через цикл. Но всё же со временем я напишу рекурсивный код. 0

go 3646 / 1378 / 243 Регистрация: 16.04.2009 Сообщений: 4,526
	03.12.2011, 20:35	21
	Сообщение от dimcoder Гуууугл? http://rain.ifmo.ru/cat/view.p... tions-2000 Добавлено через 1 минуту Можно еще с помощью рекурсии 1

	04.12.2011, 09:58