# 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
bbab
aaba
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 :)

LVL 2
###### 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.

Commented:
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?

-bcl
Commented:
I lied:

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

-bcl
Commented:
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.
-bcl
Software ArchitectCommented:
http://www.codeproject.com/cpp/cppperm1.asp
http://www.codeproject.com/cpp/permute.asp
But I guess it is a homework, anyway them are good introductorial articles.
Commented:
jaime_olivares  - That first article is pretty nice showing how next_permutation might work.

-bcl
Author Commented:

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...
Commented:
Cool.

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,
-bcl
Author 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?
Commented:
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.

-bcl
Software ArchitectCommented:
Sure you can, we don't use to sleep ;o)
Author Commented:
OK! Chers mate.... I'm not soo keen in sleeping eighter :)
Author 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...
Commented:
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)

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?

-bcl
Author 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...
Commented:
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) {
}

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.

-bcl
Author Commented:
OK! That's now clear to mee....

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

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:

bca
bac
cba
cab
abc
acb

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).
-bcl

Experts Exchange Solution brought to you by