Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.62/58: Рейтинг темы: голосов - 58, средняя оценка - 4.62
dimcoder
Полярный
467 / 440 / 157
Регистрация: 11.09.2011
Сообщений: 1,142
#1

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

03.12.2011, 11:51. Просмотров 10567. Ответов 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
Ответы с готовыми решениями:

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

Вывести все возможные перестановки слов в предложении
С клавиатуры пишем предложение. Вывести все возможные перестановки тех слов в...

Все возможные перестановки элементов заданного массива
Помогите вывести на консоль все возможные перестановки элементов заданного...

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

Рекурсивная функция: все возможные перестановки символов строки
Дана строка с n элементами. Например abs. Надо выводить все возможные варианты...

22
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 11:53 #2
А буквы в слове могут повторяться?
0
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 11:53 #3
Для начала сортируете все буквы в слове, а потом с помощью рекурсии выводите

(это алгоритм, как и просили)
0
dimcoder
Полярный
467 / 440 / 157
Регистрация: 11.09.2011
Сообщений: 1,142
03.12.2011, 12:00  [ТС] #4
Цитата Сообщение от Thinker Посмотреть сообщение
А буквы в слове могут повторяться?
Да, могут.

Цитата Сообщение от AncinetHero Посмотреть сообщение
потом с помощью рекурсии выводите
А с этого момента, поподробнее, пожалуйста.

Цитата Сообщение от AncinetHero Посмотреть сообщение
(это алгоритм, как и просили)
Ща исправим
0
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 12:26 #5
Опять алгоритм:
У вас есть функция, которая находит все перестановки и сразу выводит.
Сначала вы ей даете массив char'ов и переменную (допустим b, которая показывает сколько символов с конца мы рассматриваем). И в этой функции полно обращений к такому же массиву и уменьшенной переменной и к массиву, где мы меняем переменные...обьяснить сложно, нужно писать.
Может вы идею уловите по моему краткому комментарию (хотя, скорее всего, мой алгоритм не самый простой)
1
dimcoder
Полярный
467 / 440 / 157
Регистрация: 11.09.2011
Сообщений: 1,142
03.12.2011, 12:36  [ТС] #6
Цитата Сообщение от AncinetHero Посмотреть сообщение
нужно писать.
Был бы очень благодарен...
0
go
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 13:48 #7
Лучший ответ Сообщение было отмечено как решение

Решение

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/* Vuvesti vse perestanovki*/
#include <stdio.h>
#include <conio.h>
 
 
int str_len (char *s)
{ int i;
    for (i=0; s[i]; i++)
             ;
  return i;
}
void sort_bubl (char *s, int N)     // sortirovka puzirkom
{
    int i,j;
    char buf;
 
    for ( i=0;i<N;i++)              // cikl sortirovki
     for ( j=N-1;j>i;j--)
     if (s[j]<s[j-1])
     {
         buf=s[j]; //zamena
         s[j]=s[j-1];
         s[j-1]=buf;
     }
 
}
 
int main ()
{ char s[6], buf;
  int i,j,N,k,q;  
  clrscr ();
  puts ("Vuvesti vse perestanovki\nVvedite stroku s: ");
  fflush (stdin); scanf ("%s", &s);
  N=str_len(s);
  printf ("\nDlina stroki N=%d", N);
  puts ("\nVse vozmozhnuye perestenovki: ");
 
  sort_bubl (s, N);
 
  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;
     }
 
  }
 
 
  fflush (stdin); 
  getch ();
  return 0;
}
Писал для Борланда
6
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 17:20 #8
У меня возникает вопрос, похожий на вопрос ТС. Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
0
go
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 17:25 #9
Цитата Сообщение от AncinetHero Посмотреть сообщение
У меня возникает вопрос, похожий на вопрос ТС. Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
А у меня какой длины

Добавлено через 2 минуты
Thinker, а какая разница, нужно учесть все
0
AncinetHero
49 / 49 / 12
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 17:26 #10
Я имел в виду всех длин от 1 до длины строки
То есть для 'abc' будет
a
b
c
ab
ac
ba
bc
ca
cb
abc
0
go
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 17:31 #11
AncinetHero, выделяете из моего кода функцию перестановок, а потом отправляете
C
1
2
3
4
5
6
for (int i=1, char *ss =NULL; i<=strlen(s);i++)
{ 
         ss=strdum (s);
         ss[i]='\0';
         perest (ss);
}
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.12.2011, 17:32 #12
Цитата Сообщение от AncinetHero Посмотреть сообщение
Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
Это невозможно, т.к. всего различных перестановок будет n!, где n - длина строки.
Т.е. для строки в 10 символов будет уже 3628800 различных вариантов. А это довольно много.
Точнее правильный алгоритм будет работать для строки любой длины, но для строки длиной ~20 символов дождаться результата будет крайне сложно + переполнится стэк из-за рекурсии.
0
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
03.12.2011, 17:33 #13
AncinetHero, это уже получается вывести все сочетания по всем наборам элементов
0
go
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 17:33 #14
Цитата Сообщение от diagon Посмотреть сообщение
Это невозможно, т.к. всего различных перестановок будет n!, где n - длина строки.
ну ему может все 3-4 надо
0
Nameless One
Эксперт С++
5785 / 3434 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
03.12.2011, 17:51 #15
Цитата Сообщение от Nameless One Посмотреть сообщение
AncinetHero, это уже получается вывести все сочетания по всем наборам элементов
вот без учета порядка элементов:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
bool next_combination (std::vector<size_t>& a, size_t k)
{
    int n = (int) a.size();
    for (int i=k-1; i>=0; --i)
    {
    if (a[i] < (int) (n-k+i))
    {
        ++a[i];
        for (int j = i + 1; j < (int)k; ++j)
        a[j] = a[j-1] + 1;
        return true;
    }
    }
    
    return false;
}
 
void dump(const std::string& str, const std::vector<size_t>& indices, size_t k)
{
    for(size_t i = 0; i < k; ++i)
    putchar(str[indices[i]]);
    putchar('\n');
}
 
class nat
{
public:
    nat();
    size_t operator () ();
 
private:
    size_t curr;
};
 
nat::nat()
    : curr(0)
{
}
 
size_t nat::operator () ()
{
    return curr++;
}
 
int main()
{
    std::string str = "abc";
 
    size_t size = str.size();
 
    for(size_t i = 1; i <= size; ++i)
    {
    std::vector<size_t> indices(size);
    std::generate(indices.begin(), indices.end(), nat());
 
    do
    {
        dump(str, indices, i);
    }
    while(next_combination(indices, i));
    }
                
    return 0;
}
1
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 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
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 18:03 #17
Thinker, то, что и должна
Код
aaa
1
Миниатюры
Все возможные перестановки букв слова - нужен алгоритм  
dimcoder
Полярный
467 / 440 / 157
Регистрация: 11.09.2011
Сообщений: 1,142
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
Эксперт С++
3637 / 1369 / 243
Регистрация: 16.04.2009
Сообщений: 4,527
03.12.2011, 20:25 #19
dimcoder, алгоритм нет, код сам писал
1
dimcoder
Полярный
467 / 440 / 157
Регистрация: 11.09.2011
Сообщений: 1,142
03.12.2011, 20:28  [ТС] #20
Спрашиваю потому-что сам долго думал над алгоритмом, результат я задал на форуме

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

PS ещё раз спасибо
0
03.12.2011, 20:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2011, 20:28

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

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

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


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

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

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