Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 11:53     Все возможные перестановки букв слова - нужен алгоритм #2
А буквы в слове могут повторяться?
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 11:53     Все возможные перестановки букв слова - нужен алгоритм #3
Для начала сортируете все буквы в слове, а потом с помощью рекурсии выводите

(это алгоритм, как и просили)
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
03.12.2011, 12:00  [ТС]     Все возможные перестановки букв слова - нужен алгоритм #4
Цитата Сообщение от Thinker Посмотреть сообщение
А буквы в слове могут повторяться?
Да, могут.

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

Цитата Сообщение от AncinetHero Посмотреть сообщение
(это алгоритм, как и просили)
Ща исправим
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 12:26     Все возможные перестановки букв слова - нужен алгоритм #5
Опять алгоритм:
У вас есть функция, которая находит все перестановки и сразу выводит.
Сначала вы ей даете массив char'ов и переменную (допустим b, которая показывает сколько символов с конца мы рассматриваем). И в этой функции полно обращений к такому же массиву и уменьшенной переменной и к массиву, где мы меняем переменные...обьяснить сложно, нужно писать.
Может вы идею уловите по моему краткому комментарию (хотя, скорее всего, мой алгоритм не самый простой)
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
03.12.2011, 12:36  [ТС]     Все возможные перестановки букв слова - нужен алгоритм #6
Цитата Сообщение от AncinetHero Посмотреть сообщение
нужно писать.
Был бы очень благодарен...
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
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;
}
Писал для Борланда
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 17:20     Все возможные перестановки букв слова - нужен алгоритм #8
У меня возникает вопрос, похожий на вопрос ТС. Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 17:25     Все возможные перестановки букв слова - нужен алгоритм #9
Цитата Сообщение от AncinetHero Посмотреть сообщение
У меня возникает вопрос, похожий на вопрос ТС. Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
А у меня какой длины

Добавлено через 2 минуты
Thinker, а какая разница, нужно учесть все
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
03.12.2011, 17:26     Все возможные перестановки букв слова - нужен алгоритм #10
Я имел в виду всех длин от 1 до длины строки
То есть для 'abc' будет
a
b
c
ab
ac
ba
bc
ca
cb
abc
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
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);
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.12.2011, 17:32     Все возможные перестановки букв слова - нужен алгоритм #12
Цитата Сообщение от AncinetHero Посмотреть сообщение
Как можно реализовать алгоритм, чтобы он находил все возможные перестановки ЛЮБОЙ длины?
Это невозможно, т.к. всего различных перестановок будет n!, где n - длина строки.
Т.е. для строки в 10 символов будет уже 3628800 различных вариантов. А это довольно много.
Точнее правильный алгоритм будет работать для строки любой длины, но для строки длиной ~20 символов дождаться результата будет крайне сложно + переполнится стэк из-за рекурсии.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.12.2011, 17:33     Все возможные перестановки букв слова - нужен алгоритм #13
AncinetHero, это уже получается вывести все сочетания по всем наборам элементов
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 17:33     Все возможные перестановки букв слова - нужен алгоритм #14
Цитата Сообщение от diagon Посмотреть сообщение
Это невозможно, т.к. всего различных перестановок будет n!, где n - длина строки.
ну ему может все 3-4 надо
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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!}
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 18:03     Все возможные перестановки букв слова - нужен алгоритм #17
Thinker, то, что и должна
Код
aaa
Миниатюры
Все возможные перестановки букв слова - нужен алгоритм  
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
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, вы сами алгоритм придумали? Интересно просто.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:25     Все возможные перестановки букв слова - нужен алгоритм #19
dimcoder, алгоритм нет, код сам писал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2011, 20:28     Все возможные перестановки букв слова - нужен алгоритм
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
dimcoder
Полярный
 Аватар для dimcoder
449 / 422 / 66
Регистрация: 11.09.2011
Сообщений: 1,108
03.12.2011, 20:28  [ТС]     Все возможные перестановки букв слова - нужен алгоритм #20
Спрашиваю потому-что сам долго думал над алгоритмом, результат я задал на форуме

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

PS ещё раз спасибо
Yandex
Объявления
03.12.2011, 20:28     Все возможные перестановки букв слова - нужен алгоритм
Ответ Создать тему
Опции темы

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