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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
13.04.2011, 20:14     Следующая анаграмма строки в лексикографическом порядке #1
Условие
Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если из данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму.
Формат входных данных
Задана последовательность слов, по одному слову в строке. Длина одного слова не превышает 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;
}
Что не так?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2011, 20:14     Следующая анаграмма строки в лексикографическом порядке
Посмотрите здесь:

Выполнить сортировку строк файла в обратном лексикографическом порядке C++
C++ сортировка слов в строке в лексикографическом порядке (по алфавиту)
C++ Алгоритм генерации перестановок в лексикографическом порядке
C++ Проверить, что все слова заданной строки упорядочены в лексикографическом порядке (как в словаре)
C++ Генерация сочетаний из k элементов по n в лексикографическом порядке
C++ упорядочить строки в лексикографическом порядке
Переставить слова, расположив их в лексикографическом порядке C++
C++ Перечисление перестановок порядка n в лексикографическом порядке

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
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;
}
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 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] до конца?
Yandex
Объявления
13.04.2011, 22:33     Следующая анаграмма строки в лексикографическом порядке
Ответ Создать тему
Опции темы

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