String Algorith

Well Experts...

The is this:

I 'm going to take a string from the user... And then I'm going to present the number of diffrent outputs it can generate...
Like this:

User writes: abab
Program writes
and so on...
changing the places of the letters, and a letter can not be moved to the same place or another place where it's the same letter...

I would need some help on how to write this algorith....
Some tips would be great :)

Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Well, the permute() algorithm in the STL will produce all of the permutations. You could keep them in a set so that abba (first a, first b, second b and second a) is not printed along with abba (second a, first b, second b, first a).

Or do you have to write the code for yourself?

I lied:

use next_permutation(str.begin(), str.end()) to generate the next permutation of the string.

I am going to ask my standard question: Is this a homework assignment? If so, I don't want to show you the answer but instead help you design and implement your own algorithm. If all you want is the set of unique permutations, that is actually easy to generate.

Let us know what you need.
CompTIA Security+

Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

Jaime OlivaresSoftware ArchitectCommented:
Some tutorials about STL permutations:
But I guess it is a homework, anyway them are good introductorial articles.
jaime_olivares  - That first article is pretty nice showing how next_permutation might work.

SnurreAuthor Commented:
to bcladd:

1.  NO It's not a home assignment... It's a crasy kid *that's me* that love to solve some odd probles with programming :)
2. I Would like to write the Code myself... That's the hole chalange, and by the way, I have never used STL...
3. I'm going to look at the links you posted...

The first link above (from jaime_olivares) includes code that describes how to generate all of the permutations (either recursively or iteratively).

If you loop through all of the permutations you can extract all of the unique permutations by keeping a collection of the permutations so far and only inserting a new one if it is not already present. If you use the STL (I urge you to learn to use the STL as it will make it easier to solve difficult problems and besides, it is fun) you can get this behavior with set; if you write your own container you have a problem in that you don't know how many unique permutations there will be (okay, you can figure it out by determing the number of permutations and then dividing by the product of all of the permutations of identical elements; then you can dynamically alocate an array of the right size before you start). You could use a linked list to hold all of the permutations and scan it, inserting if you reach the end without matching.

Hope this helps,
SnurreAuthor Commented:
OK! Now I know what to do this friday night :) i'm going to try some stuff out, and by the way, If or when I Get stuck, may I ask for some guidence then or?
Cool. I have the STL version running in ~30 lines (I get set and next_permutation for free).

Let me know if you need any help.

Jaime OlivaresSoftware ArchitectCommented:
Sure you can, we don't use to sleep ;o)
SnurreAuthor Commented:
OK! Chers mate.... I'm not soo keen in sleeping eighter :)
SnurreAuthor Commented:
OK Guys....

I have been trying some stuff, but this was harder than I thought.....
I Coul'd actually need some samples or some more detailed directions...
Well, I am not sure what you want. I can give you the STL solution. Then, if you want to play at generating permutations, you can replace the next_permutation  call with a call of your own.

Basically the structure of the program is:

  get string str;
  while there is another permutation of the str
    if (collection does not include permutation)
      add permutation to collection

   foreach entry in collection
      print entry

Does that make sense? The hard part is generating all of the permutations. The other challenging part is a colletion that has no duplicates.

What do you want to talk about first?

SnurreAuthor Commented:
Well, firts thing first... :)

I Would need some tips on the Colletion and how to insert without having any duplicates.... I find this the most important for the moment...
Okay. I am going to use the STL vector. A vector is just an array that can dynamically size itself. We want to store strings in a vector. Then I will write an addIfNotPresent function that will add a string to the vector if and only if that string is not in the vector. I am going to be showing you the code as an example along with some comments.

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

using namespace std; // don't need std:: infront of
                     // everything (like string, vector)

/* return true if added candidate to collection; false if collection already
   has the candidate in it.
bool addIfNotPresent(vector<string> & collection, const string & candidate)
  bool present = false; // assume it isn't present

  for (unsigned int i = 0; !present && i != collection.size(); ++i) {
    if (collection[i] == candidate) // candidate is already in the collection! get out of loop
      present = true;

  // append the candidate to the end of the vector (that is what push_back does) IF and ONLY IF
  // it was not already in the collection.
  if (!present)
    collection.push_back(candidate); // append candidate to end of vector

  return !present; // value of function is inverse of whether the candidate was present.

int main()
      // the word read from the user
  string word;
      // a vector is a template so we include the type between angle brackets
  vector<string> V;

      // read words from user and insert them (without duplicates) into V
  while (cin >> word) {
    addIfNotPresent(V, word);

  for (unsigned int i = 0; i != V.size(); ++i) {
    cout << V[i] << endl;

Similar code can be used with an array (there you need to keep track of the size yourself). The set template basically does this for you (with a more efficient method for checking for duplicates).

You might want to look up iterators, too, since they can make the loops easier to write for other STL containers.

SnurreAuthor Commented:
OK! That's now clear to mee....

So, generating all of the permutations. Some tip on that.... :)

Given a string (I will probably slip in the following and call it an array, too. It is, effectively, an array of characters; read string when I say array) of length n, how could we enumerate all of the permutations?

Well, we could pick one of the n characters for the first position. Then, how could we enumerate all of the permutations that begin with that character? Hmmm... seems like we could just follow that first character with ALL of the permutations of the remaining n-1 characters. Does that make sense? For each i, choose a character for position i, and generate all permutations following i.

For "bca" the permutations are:


How could we write a function to do that? That is, to list all of the permutations? We could use recursion. That is, use one function to permute the suffix of any string. To use recursion we need a base case and a way of defining a problem in terms of a smaller case. How about suffix of length 0 for the base case and the smaller case is fixing one char and recurring on the suffix after that char. The following is pseudocode:

void permuteAndPrint(string str, int suffixNdx) {
  if (suffixNdx >= str.length()) // base case
    cout << str << endl;
  else {
    for (int i = suffixNdx; i < str.length(); ++i) {
      swap(str[suffixNdx], str[i]); // pick one of the char for the remaining position
      permuteAndPrint(str, suffixNdx+1);
      swap(str[i], str[suffixNdx]); // put characters back as they were for next time through the loop

Hope this makes sense (see the first link above for more on permutation).

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
SnurreAuthor Commented:
OK! I have solved my problem.... Now it works as it is supposed, and I have pushed some new knowledge into my big array... :)

Tanks for the Support and all the help bcladd :) Could't have done it without you *grateful*

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.