Paste will expire never.
- // Меньшиков. Тренировка 3.
- // 3B. Перестановки (2) [permut2]
- // Решение идентично 2B по принципу next_permutation
- // ibelyaev: 02Mar2010
- #include <iostream>
- #include <string>
- #include <algorithm>
- using namespace std;
- string str;
- void input()
- {
- cin>>str;
- }
- bool next_permutation(string &str)
- {
- // находим элемент меньше или равного последующему
- int pos = -1;
- for (int i=str.size()-2;i>=0;i--)
- if (str[i] < str[i+1])
- {
- pos = i;
- break;
- }
- if (pos == -1)
- return false; // текущая перестановка последняя в лексикографическом порядке
- // находим минимальный элемент превышающий найденый
- char value = str[pos];
- int swapIndex = -1;
- for (int i=str.size()-1;i>=pos;i--)
- if (str[i]>value)
- {
- swapIndex = i;
- break;
- }
- swap(str[pos],str[swapIndex]);
- //реверс подстроки правее индекса pos
- int f = pos+1, s = str.size()-1;
- while (f<s)
- swap(str[f++],str[s--]);
- return true;
- }
- void solve()
- {
- sort(str.begin(),str.end());
- cout<<str<<endl;
- while (next_permutation(str))
- cout<<str<<endl;
- }
- int main()
- {
- input();
- solve();
- return 0;
- }
Editing is locked.