Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 62, средняя оценка - 4.61
dimcoder
Полярный
466 / 439 / 68
Регистрация: 11.09.2011
Сообщений: 1,138
#1

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

03.12.2011, 11:51. Просмотров 9249. Ответов 22
Метки нет (Все метки)

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

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

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

Найти все возможные варианты написания слова в верхнем и нижнем регистрах букв. - C++
Хотелось бы увидеть кусочек кода, который выполнял бы следующее: Есть слово "Напримерэто". Как мне вывести на экран (в файл, принтер - без...

Все возможные перестановки элементов заданного массива - C++
Помогите вывести на консоль все возможные перестановки элементов заданного массива void printPermutations (int items , int itemsLength) {...

Все возможные варианты перестановки символов строки - C++
Дана строка s, состоящая из n символ (n меньше 6) составить все возможные варианты перестановки этих символов (язык C)

Вывести все возможные перестановки слов в предложении - C++
С клавиатуры пишем предложение. Вывести все возможные перестановки тех слов в этом предложении, что не содержат первых десяти букв...

Рекурсивная функция: все возможные перестановки символов строки - C++
Дана строка с n элементами. Например abs. Надо выводить все возможные варианты например abs asb bas bsa sab sba. Надо...

Вывести на экран все возможные перестановки введенных ползователем символов - C++
С клавиатуры задается последовательность символов. Написать программу, которая выводит на экран все возможные перестановки введенных...

22
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 18:01 #16
Цитата Сообщение от go Посмотреть сообщение
Thinker, а какая разница, нужно учесть все
Если нет повторяющихся элементов, то обычные перестановки легче реализовать. Если строка s="aaa"
ваша программа что выведен на экран?

Цитата Сообщение от diagon Посмотреть сообщение
всего различных перестановок будет n!
Немного поправлю. Если в слове k букв и буква a1 повторяется n1 раз,... ak повторяется nk раз, то перестановок всего
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n!}{n_1!...n_k!}
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 18:03 #17
Thinker, то, что и должна
Код
aaa
1
Миниатюры
Все возможные перестановки букв слова - нужен алгоритм  
dimcoder
Полярный
466 / 439 / 68
Регистрация: 11.09.2011
Сообщений: 1,138
03.12.2011, 20:17  [ТС] #18
Спасибо всем. Буду пока вникать в код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while (1) 
{ 
   // nachinaem perebirat' vse vozmozhnuye perestanovki
   printf("%s\n", s); 
   // vuvod ocherednoy perestanovki
   for (i = N-2; i >= 0 *&& s[i] >= s[i+1] ; i--); 
   // nahodim samoe pravoe mesto, gde s[i] < s[i+1]
   if (i<0) 
       break; // uze poluchili vse perestanovki
   for(j=N-1; s[i] >= s[j]; j--) ;  
   // nahodim s[j] - naimenshuy element spravo ot s[i] i bolshe ego
   // menyaem s[i] - *s[j]
   buf = s[j];
   s[j] = s[i];
   s[i] = buf;
// obraschaem el-ntu spravo ot s[i]
   for ( k=i+1, q=N-1; k < q; k++ , q-- )
   {
       buf=s[k];
       s[k]=s[q];
       s[q]=buf;
   }
}
Вроде всё понятно, надо запомнить. Кстати, go, вы сами алгоритм придумали? Интересно просто.
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:25 #19
dimcoder, алгоритм нет, код сам писал
1
dimcoder
Полярный
466 / 439 / 68
Регистрация: 11.09.2011
Сообщений: 1,138
03.12.2011, 20:28  [ТС] #20
Спрашиваю потому-что сам долго думал над алгоритмом, результат я задал на форуме

Цитата Сообщение от go Посмотреть сообщение
dimcoder, алгоритм нет, код сам писал
Гуууугл?

PS ещё раз спасибо
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:35 #21
Цитата Сообщение от dimcoder Посмотреть сообщение
Гуууугл?
http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000

Добавлено через 1 минуту
Можно еще с помощью рекурсии
1
dimcoder
Полярный
466 / 439 / 68
Регистрация: 11.09.2011
Сообщений: 1,138
04.12.2011, 09:17  [ТС] #22
Цитата Сообщение от go Посмотреть сообщение
http://rain.ifmo.ru/cat/view.php/vis...mutations-2000
Спасибо за ссылку, полезно.
Цитата Сообщение от go Посмотреть сообщение
Можно еще с помощью рекурсии
Предпочитаю, как то без этих рекурсий делать. Они память грузят. Говорят, мол, красиво через рекурсию - для меня пока запутанно больше. Да и потом, любую задачу, которую можно решить рекурсивно, можно решить и через цикл. Но всё же со временем я напишу рекурсивный код.
0
Байт
Эксперт C
16555 / 10825 / 1640
Регистрация: 24.12.2010
Сообщений: 20,910
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;
   }
 }
}
/*****************/
Нашел в книге Липского "Комбинаторика для программистов"
2
04.12.2011, 09:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2011, 09:58
Привет! Вот еще темы с ответами:

Вывести на экран все возможные перестановки введенных символов. Где ошибка? - C++
С клавиатуры задается последовательность символов. Написать программу, которая выводит на экран все возможные перестановки введенных...

Ввести число. Используя рекурсивную функцию, получить все возможные перестановки цифр этого числа - C++
Помогите пожалоста..........Заранеє спасибо

Сформировать все возможные слова, получаемые из данного слова - C++
допустим ввожу слово: asdf прога должна вывести: a s d f aa as ad af

Дано n различных чисел, напечатать все возможные перестановки этих чисел - C++
Помогите пожалуйста решить задачу через рекурсию: Дано n различных чисел, напечатать все возможные перестановки этих чисел.


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru