v 0. Pasted by slipstak2 as cpp at 2011-02-08 13:25:00 MSK and set expiration to never.

Paste will expire never.

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <string>
  5. using namespace std;
  6.  
  7.  
  8. bool next_permutation_swap(vector<int> &p,  // перестановка
  9.                            vector<int> &y,  // таблица инверсий
  10.                            vector<int> &d) // направление движений
  11. {
  12.     int n = p.size();
  13.     int i;
  14.     int next = 0;
  15.     for (i=n-1;i>=0;i--) {
  16.         int border = d[i] == 1 ? i : 0;
  17.         if (y[i] != border) {
  18.             y[i] += d[i];
  19.             next = d[i];
  20.             break;
  21.         }
  22.         else
  23.             d[i] = -d[i];
  24.     }
  25.     if (!next) // последняя перестановка
  26.         return false;
  27.     for (int j = 0; j < n; j++)
  28.         if (p[j] == i) {
  29.             swap(p[j],p[j+d[i]]);
  30.             break;
  31.         }
  32.     return true;
  33. }
  34.  
  35. int main()
  36. {
  37.     freopen("input.txt","r",stdin);
  38.     freopen("output.txt","w",stdout);
  39.  
  40.     string a;
  41.     cin>>a; // можно не сортить
  42.     int n = a.size();
  43.     vector<int> p(n);   // перестановка
  44.     vector<int> y(n);   // таблица инверсий
  45.     vector<int> d(n,1); // направление движений
  46.     for (int i=0;i<n;i++)
  47.         p[i] = n-1-i;
  48.  
  49.     do
  50.     {
  51.         for (int i=0;i<n;i++)
  52.             cout<<a[p[i]];
  53.         cout<<endl;
  54.     } while (next_permutation_swap(p,y,d));
  55.  
  56.     return 0;
  57. }


Editing is locked.