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 :)
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).
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
This course will introduce you to C++ 11 and teach you about syntax fundamentals.
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.
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?
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.
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.
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.
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
This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.
Or do you have to write the code for yourself?
-bcl