Thread: permutations

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    35

    permutations

    I'm trying to give my program some letters and have it "jumble" them around to find words. This means I need to find all permutations of all 'lengths' of the word. My program seems to find the first "level" of permutations fine. However, the second "level" (where I chop off a letter and find all permutations of the smaller set of letters) seems to have a problem. I think it has something to do with missing a '\0' at the end, because when I print it, it prints a bunch of jibberish until it eventually seg faults. The first "level" prints just fine.

    Code:
    //#include "wordlist.h"
    #ifndef JUMBLER_H
    #define JUMBLER_H
    
    #include <string>
    #include <vector>
    #include <algorithm>
    #include "wordlist.h"
    
    #include <iostream>
    
    using namespace std;
    
    class Jumbler
    {
          public:
          Jumbler();
          
      
          WordList jumble(const string &);
                       
          private:
          WordList allWords;
          vector<char> make_vector(string );
          string make_string(vector<char> );         WordList all_perms(vector<char>); 
        
          
    };
    
    //The one and only public method
    //it's supposed find all permutations 
    //of a set of letters, cut off a letter,
    //and then find all permutations of
    //the remaining letters
    WordList Jumbler::jumble(const string &str)
    {
         int size = str.size(); 
         int i = 0;
         WordList wl;  
    
         //must use vector (instead of strings) for next_permutation()
         vector<char> vch; 
         string temp;
         
         while(size)
         {
                //chop off letter
                //get the substring from index 0 to "one less"
                temp = str.substr(0, --size);
                temp += '\0';  //ensure null terminator
    
                //convert string to a vector 
                vch = make_vector(temp); 
    
                //appends a list of words to a list of words -- i'm pretty confident with this method
                wl.append(all_perms(vch));
                //i++;          
         } 
         allWords = wl;
         return allWords;
    }
    
    //finds all permutations of a set of letters
    //adds them to a list, and then returns a list
    WordList Jumbler::all_perms(vector<char> original)
    {
             WordList wl;
             sort(original.begin(), original.end());
             while(next_permutation(original.begin(), original.end()) )
             {
                                                      
                  wl.add( make_string(original) );
             }
             
             return wl;
    }
    
    
    //converts string to vector
    string Jumbler::make_string(vector<char> s)
    {
           string r;
           int i = 0;
            for(; i < s.size(); i++)
                    r += s[i];
            i++;
            s[i] = '\0';
           
            
           return r;       
    }
    
    //converts vector to string
    vector<char> Jumbler::make_vector(string s)
    {
           vector<char> r;
            for(int i = 0; i < s.size(); i++)
                    r.push_back(s[i]);
            return r;       
    }
    
    
    #endif

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> must use vector (instead of strings) for next_permutation()
    Why? The string class should work with next_permutation just fine.

    Inside make_string, you set s[i] = '\0';. You probably meant r there, but either way it doesn't matter. The string class doesn't need the terminating null, and adding one will mess things up because the null character will be permuted like the other characters. You wouldn't need a terminating null character in the vector either, if you actually needed a vector for this.

    The terminating null is just a way to remember the size of a C style string, since C style arrays don't know their size when passed around. C++ strings and vectors keep track of their own size.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    35
    Quote Originally Posted by Daved

    The string class doesn't need the terminating null, and adding one will mess things up because the null character will be permuted like the other characters.
    good point. originally i didn't add the '\0'. i put that in out of desperation at 4 o'clock in the morning.

    I remember trying to use next_permutation with strings about a year ago. If I remember correctly, I couldn't do it.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It should be exactly the same as with the vector. Both strings and vectors have the same member functions begin() and end() that you use with next_permutation.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  2. recursive permutations
    By wd_kendrick in forum C Programming
    Replies: 7
    Last Post: 06-02-2008, 03:11 PM
  3. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 AM
  4. String permutations help
    By nickk in forum C Programming
    Replies: 4
    Last Post: 05-15-2004, 01:55 PM
  5. Permutations
    By kiddy in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2002, 09:53 AM