Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 62, средняя оценка - 4.61
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
03.12.2011, 11:51     Все возможные перестановки букв слова - нужен алгоритм #1
Доброго времени суток, форумчане. Помогите пожалуйста найти/составить алгоритм решения следующей задачи:
Дано слово. Найти все возможные варианты перестановки его букв.

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

PS Встречал я кое-где решение с next_permutation, но мне важно решить без всяких левых функций.
PSS Ну и программу по ходу дела смастерить тоже нужно
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2011, 11:51     Все возможные перестановки букв слова - нужен алгоритм
Посмотрите здесь:

C++ Найти все возможные варианты написания слова в верхнем и нижнем регистрах букв.
C++ Все возможные варианты перестановки символов строки
C++ Все возможные перестановки элементов заданного массива
C++ Ввести число. Используя рекурсивную функцию, получить все возможные перестановки цифр этого числа
Вывести на экран все возможные перестановки введенных ползователем символов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:35     Все возможные перестановки букв слова - нужен алгоритм #21
Цитата Сообщение от dimcoder Посмотреть сообщение
Гуууугл?
http://rain.ifmo.ru/cat/view.php/vis...mutations-2000

Добавлено через 1 минуту
Можно еще с помощью рекурсии
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
04.12.2011, 09:17  [ТС]     Все возможные перестановки букв слова - нужен алгоритм #22
Цитата Сообщение от go Посмотреть сообщение
http://rain.ifmo.ru/cat/view.php/vis...mutations-2000
Спасибо за ссылку, полезно.
Цитата Сообщение от go Посмотреть сообщение
Можно еще с помощью рекурсии
Предпочитаю, как то без этих рекурсий делать. Они память грузят. Говорят, мол, красиво через рекурсию - для меня пока запутанно больше. Да и потом, любую задачу, которую можно решить рекурсивно, можно решить и через цикл. Но всё же со временем я напишу рекурсивный код.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2011, 09:58     Все возможные перестановки букв слова - нужен алгоритм
Еще ссылки по теме:

Вывести на экран все возможные перестановки введенных символов. Где ошибка? C++
C++ Вывести все возможные перестановки слов в предложении
C++ Рекурсивная функция: все возможные перестановки символов строки

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
04.12.2011, 09:58     Все возможные перестановки букв слова - нужен алгоритм #23
Вот такой есть НЕРЕКУРСИВНЫЙ алгоритм
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
   }
 }
}
/*****************/
Нашел в книге Липского "Комбинаторика для программистов"
Yandex
Объявления
04.12.2011, 09:58     Все возможные перестановки букв слова - нужен алгоритм
Ответ Создать тему
Опции темы

Текущее время: 12:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru