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

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

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.

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.