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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
#1

Следующая анаграмма строки в лексикографическом порядке - C++

13.04.2011, 20:14. Просмотров 1681. Ответов 2
Метки нет (Все метки)

Условие
Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если из данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму.
Формат входных данных
Задана последовательность слов, по одному слову в строке. Длина одного слова не превышает 50 символов.
Формат выходных данных
Необходимо вывести вывести результат для каждого полученного на вход слова.
Источник

Мое решение

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
using std::string;
 
string next_lex(string s)
{
  if (s.length() < 2) return s;
 
  string r = "";
  int i = s.length() - 2;
 
  while (i >= 0 && s[i] >= s[i+1]) i--;
 
  if (i == -1)
    while (s.length()) {
      r += s[s.length() - 1];
      s.erase(s.length() - 1);
    }
  else
  {
    r = s.substr(0, i) + s[i+1];
    s = s[i] + s.substr(i + 2, s.length() - i - 2);
 
    for (int k = 0; k < s.length() - 1; k++)
      for (int l = k; l < s.length(); l++)
        if (s[k] > s[l])
        {
          char c = s[k];
          s[k] = s[l];
          s[l] = c;
        }
 
    r += s;
  }
 
  return r;
}
 
int main()
{
  string s; vector <string> a;
 
  while (!cin.eof()) { cin >> s; a.push_back(s); }
 
  for (int i = 0; i < a.size() - 1; i++)
    cout << next_lex(a[i]) << endl;
 
  return 0;
}
Что не так?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2011, 20:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Следующая анаграмма строки в лексикографическом порядке (C++):

Упорядочить строки в лексикографическом порядке - C++
нужно упорядочить строки в лексикографическом порядке. вот код, но он не выводит на экран помогите найти ошибки, пожалуйста #include...

Проверить, что все слова заданной строки упорядочены в лексикографическом порядке (как в словаре) - C++
Проверить, что все слова заданной строки упорядочены в лексикографическом порядке (как в словаре). помогите решить задачку на с++ :cry:

Сортировка в лексикографическом порядке - C++
Здравствуйте. Помогите с программой. 1. С использованием структур написать программу, в которой вводится список слов и их определений....

Распечатать перестановки в лексикографическом порядке - C++
На вводе число,например 5 На выводе 12345 23451 и тд,в общем этих чисел будет 5! (факториал) Даже идей...

Алгоритм генерации перестановок в лексикографическом порядке - C++
У меня проблема. Нужно перебрать все лексикографически следующие перестановки. Вот мой код. Одна перестановка делается, а дальше я не знаю,...

Переставить слова, расположив их в лексикографическом порядке - C++
Дан массив, содержащий символы. Группы символов, разделенные пробелами и не содержащие пробелов внутри себя, будем называть словами....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
asics
Freelance
Эксперт С++
2847 / 1784 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
13.04.2011, 21:15 #2
Можно пойти коротким путем
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
 
int main(){
  std::ifstream ifs("input.txt");
  std::ofstream ofs("output.txt");
  std::string str;
  while(!ifs.eof()){
    getline(ifs, str);
    std::next_permutation(str.begin(), str.end());
    ofs << str << '\n';
  }
  return 0;
}
2
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
13.04.2011, 22:33  [ТС] #3
Черт, такое чувство, стл выучишь, и никакая теория алгоритмов не нужна

А логика хоть верная? Находим такое i, что a[i] < a[i+1], если такого нет - выводим строку наоборот, иначе меняем a[i+1] и a[i] местами и сортируем по неубыванию часть строки с a[i+1] до конца?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2011, 22:33
Привет! Вот еще темы с ответами:

Генерация сочетаний из k элементов по n в лексикографическом порядке - C++
Помогите пожалуйста понять в чем ошибка #include&lt;iostream&gt; using namespace std; #define n 6 #define k 4 int x ; int...

Перечисление перестановок порядка n в лексикографическом порядке - C++
1. Выбор начальной перестановки π = (π1, π2, …, πn) = (1, 2, …, n). Например, π = (2, 6, 5, 8, 7, 4, 3, 1). 2. Просмотр...

Нужно разобраться в коде: палиндромы в лексикографическом порядке - C++
void nextSequence(string &amp;sequence, int k) { int i = sequence.size() - 1; while (i &gt;= 0 &amp;&amp; sequence == k - 1) { i--; } ...

Сортировка слов в строке в лексикографическом порядке (по алфавиту) - C++
Как отсортировать слова в строке в лексикографическом порядке (по алфавиту)?Помогите , пожалуйста.


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

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

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