Solved

# String Algorith

Posted on 2004-09-17
245 Views
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 :)

0
Question by:Snurre
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 9
• 7
• 2

LVL 11

Expert Comment

ID: 12085309
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
0

LVL 11

Expert Comment

ID: 12085391
I lied:

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

-bcl
0

LVL 11

Expert Comment

ID: 12085484
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
0

LVL 55

Expert Comment

ID: 12085595
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.
0

LVL 11

Expert Comment

ID: 12085658
jaime_olivares  - That first article is pretty nice showing how next_permutation might work.

-bcl
0

LVL 2

Author Comment

ID: 12086328

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...
0

LVL 11

Expert Comment

ID: 12086566
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
0

LVL 2

Author Comment

ID: 12086633
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?
0

LVL 11

Expert Comment

ID: 12086659
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
0

LVL 55

Expert Comment

ID: 12086662
Sure you can, we don't use to sleep ;o)
0

LVL 2

Author Comment

ID: 12086683
OK! Chers mate.... I'm not soo keen in sleeping eighter :)
0

LVL 2

Author Comment

ID: 12091303
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...
0

LVL 11

Expert Comment

ID: 12091541
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
0

LVL 2

Author Comment

ID: 12096137
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...
0

LVL 11

Expert Comment

ID: 12096252
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
0

LVL 2

Author Comment

ID: 12096277
OK! That's now clear to mee....

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

LVL 11

Accepted Solution

ID: 12097046
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
0

LVL 2

Author Comment

ID: 12097499
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*

0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [sâ€¦
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article locâ€¦
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
###### Suggested Courses
Course of the Month6 days, 15 hours left to enroll