#include<set>
#include<string>
#include<iostream>

using namespace std;

void permutate(string left, string cur, set<string>& subset)
{
  if (cur.length() && subset.find(cur) == subset.end())
    subset.insert(cur);

  if (left.length() == 0)
    return;

  for (int i = 0; i < left.length(); i++)
  {
    string r = left;
    cur.push_back(left[i]);
    r.erase(i, 1);
    permutate(r, cur, subset);
    cur.pop_back();
  }
}

set<string> find_all_permutation(string input)
{
  set<string> subset;
  permutate(input, "", subset);
  return subset;
}

int main()
{
  string input = "abcd";
  set<string> result = find_all_permutation(input);
  set<string>::iterator iter;
  for(iter = result.begin(); iter != result.end(); iter++)
    cout<< *iter <<endl;
  return 1;
}