#include <iostream>
#include <string>
#include <vector>

using namespace std;

/**
   Generuje wszystkie permutacje znaków ciągu.
   @param word ciąg
   @return wektor zawierający wszystkie permutacje
   danego wyrazu
*/
vector<string> generate_permutations(string word)
{
   vector<string> result;
   if (word.length() == 0) 
   {
      result.push_back(word); // Permutacją ciągu pustego jest tylko on sam.
      return result;
   }

   for (int i = 0; i < word.length(); i++)
   {
      string shorter_word = word.substr(0, i)
         + word.substr(i + 1); // Wyraz bez litery nr i
      vector<string> shorter_permutations
         = generate_permutations(shorter_word);

      // Dodaj literę nr i na początek wszystkich permutacji krótszego wyrazu.
      for (int j = 0; j < shorter_permutations.size(); j++)
      {
         string longer_word = word[i] + shorter_permutations[j];
         result.push_back(longer_word);
      }   
   }
   return result;
}

int main()
{
   cout << "Wprowadź ciąg: ";
   string input;
   getline(cin, input);   
   vector<string> v = generate_permutations(input);
   for (int i = 0; i < v.size(); i++)
   {
      cout << v[i] << endl;
   }
   return 0;
}

