Solved

String Algorith

Posted on 2004-09-17
18
240 Views
Last Modified: 2010-04-01
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
Comment
Question by:Snurre
  • 9
  • 7
  • 2
18 Comments
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
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

by:bcladd
Comment Utility
I lied:

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

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
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

by:Jaime Olivares
Comment Utility
Some tutorials about STL permutations:
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

by:bcladd
Comment Utility
jaime_olivares  - That first article is pretty nice showing how next_permutation might work.

-bcl
0
 
LVL 2

Author Comment

by:Snurre
Comment Utility
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...
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
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

by:Snurre
Comment Utility
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

by:bcladd
Comment Utility
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
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
LVL 55

Expert Comment

by:Jaime Olivares
Comment Utility
Sure you can, we don't use to sleep ;o)
0
 
LVL 2

Author Comment

by:Snurre
Comment Utility
OK! Chers mate.... I'm not soo keen in sleeping eighter :)
0
 
LVL 2

Author Comment

by:Snurre
Comment Utility
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

by:bcladd
Comment Utility
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?

-bcl
0
 
LVL 2

Author Comment

by:Snurre
Comment Utility
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

by:bcladd
Comment Utility
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.

-bcl
0
 
LVL 2

Author Comment

by:Snurre
Comment Utility
OK! That's now clear to mee....

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

Accepted Solution

by:
bcladd earned 150 total points
Comment Utility
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

by:Snurre
Comment Utility
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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now