v 0. Pasted by UnderFelixAbove as cpp at 2010-05-18 22:04:07 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 3.
  2. // 3B. Перестановки (2) [permut2]
  3. // Решение идентично 2B по принципу next_permutation
  4. // ibelyaev: 02Mar2010
  5.  
  6. #include <iostream>
  7. #include <string>
  8. #include <algorithm>
  9. using namespace std;
  10.  
  11. string str;
  12. void input()
  13. {
  14.     cin>>str;
  15. }
  16. bool next_permutation(string &str)
  17. {
  18.     // находим элемент меньше или равного последующему
  19.     int pos = -1;
  20.     for (int i=str.size()-2;i>=0;i--)
  21.         if (str[i] < str[i+1])
  22.         {
  23.             pos = i;
  24.             break;
  25.         }
  26.     if (pos == -1)
  27.         return false; // текущая перестановка последняя в лексикографическом порядке
  28.     // находим минимальный элемент превышающий найденый
  29.     char value = str[pos];
  30.     int swapIndex = -1;
  31.     for (int i=str.size()-1;i>=pos;i--)
  32.         if (str[i]>value)
  33.         {
  34.             swapIndex = i;
  35.             break;
  36.         }
  37.     swap(str[pos],str[swapIndex]);
  38.     //реверс подстроки правее индекса pos
  39.     int f = pos+1, s = str.size()-1;
  40.     while (f<s)
  41.         swap(str[f++],str[s--]);
  42.     return true;
  43. }
  44. void solve()
  45. {
  46.     sort(str.begin(),str.end());
  47.     cout<<str<<endl;
  48.     while (next_permutation(str))
  49.         cout<<str<<endl;
  50. }
  51. int main()
  52. {
  53.     input();
  54.     solve();
  55.     return 0;
  56. }


Editing is locked.