Arranging a word in all possible combinations

[Chazzmundo]

Hello all. I am just starting to learn C++ but have moderate experience with C. I am using the Dev-C compiler for my program.

The program I wish to create will allow the user to input a string of words each separated by a space.

It then separates these into different words e.g. "hi every person" would be split into three variables

w1 = "hi";
w2 = "every";
w3 = "person";

Ok I am not worried about this part at the moment as it currently will just take in the one word. It then has to search for this within a predefined wordlist and return whether or not it is found.

I have got this working to. The problem I have run into is as follows:

My program needs to be able to take each word and swap the letters around in every possible combination and then search for this in the wordlist (basically a descrambler).

For example the user enters: "eli"

The program then needs to search for:

"eli"
"eil"
"iel"
"ile"
"lei"
"lie" <- this is the correct word and once found it will return this as the word.

How do I program it to search for each letter in turn regardless of the amount of letters? (Yes i know high amount of letters will take a long time but at the moment it will be limited to 10 or under).

The following is the code used so far:

#include <cstdlib>
#include <iostream>
#include <string>
#include <fstream> //file handling

using namespace std;

int check(string word)
{
     string line = "";
     cout << "\n";

     ifstream file("C:/Users/Chazz & Bill/Documents/prog/input/wordlist.txt",  ios::in); //open file
        
     if (!file.is_open()) //if cant open file: close
     {
         cout << "\nUnable to open file \n";
         system("PAUSE");
         exit(1);
     }
  
  
     while(getline(file,line))
     {
        if (line == word)
        {
           cout << "Result found :)\n\n";
           return 1;         
        }
     }
        
     if (line != word)
     {
           cout << "Result NOT found :'(\n\n";
          return 0;
     }     
}


int result(string word)
{
    int len = word.length(); //length of string
    char num[len]; //how many chars there are
    int i = 0;
    cout << "\n"; 
    
    for (i=0;i <=len; i++) //set each char into an array
    {
        num[i] = word[i];
    }
    
    for (i=0;i <=len; i++) //print out each number
    {
        cout << num[i] << "\n";
    }
    
    //****start print in all directions THIS IS WHERE IT NEEDS TO DESCRAMBLE ****/
    
    
    check(word); //check word exists

 
    
    //end
    return len; //return number of letters     
}


int main(int argc, char *argv[])
{
    string input = "";
    string out = "";
    int len = 0;
    cout << "Please enter string and press enter:";
    cin >> input;
    
    len = result(input);
    
    cout << input << " is " << len << " chars \n";
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Thank you for any help you can provide :)

[Galik]

This might be of use to you:
http://www.cplusplus.com/reference/algorithm/next_permutation/

[Chazzmundo]

Thank you for the link and I feel this is the right track but how exactly would I apply this to work with a passed by value string with N amount of chars?

It uses the standard N! to work out how many combination's there are for a set amount of letters but would I have to write another function to work out exactly how many times it has to be called?

[Chazzmundo]

I have created a factorial function to work out how many permutations are needed but when I try with a string it does not reorder the letters and will print out MANY more times than needed.

What is wrong?

int factorial(int n) //work out how many combinations there are
{
      if (n < 0 || n > 12) 
      {
            cout << "Invalid range please try again"<<endl;
            return 0;      
      }
      
      switch (n)
      {
        case 0: return 1; 
        case 1: return 1;   
        default: return (n * factorial(n-1));  
      }   
      
}


int order(string word) 
{
      int len = word.length(); //length of string
      char num[len]; //how many chars there are
      int i = 0;
      cout << "\n"<<"Length of word: "<<len<<endl; 
      string temp_word = ""; //to be used for checking
      int possible_combinations = factorial(len); //work out how many combinations there are
      int myints[] = {1,2,3}; //this was what was used in article so using for test purposes
      
      
      for (i=0; i<=len; i++) //set each char into an array
      {
        num[i] = word[i];
      }
      
      cout<<"MI: "<<myints<<"\tNUM: "<<num<<endl; 
      /*ABOVE OUTPUT: testing to see what each gives, myints = hex value (0x22fe30), 
      num gives the string WHAT TO DO???*/
      
      
      cout << "The " << len <<"! possible permutations gives "<< possible_combinations <<" different combinations:\n";
    
      sort (num,num+possible_combinations);
    
      do 
      {
        for (i=0; i<=len; i++) //show each character in its order
        {
            cout << word[i] << " ";
        }
        cout << endl;
      } 
      while ( next_permutation (num,num+possible_combinations) );
      //while (i<3);
      return 0;
}

[ne555]

 //sort (num,num+possible_combinations); 
sort(num, num+len);
    
      do 
      {
        for (i=0; i<=len; i++) //show each character in its order
        {
            cout << word[i] << " ";//you modify num not word (prints always the same)
        }
        cout << endl;
      } 
      while ( next_permutation (num,num+possible_combinations) );// again     (num, num+len) 

No need to copy word into num either (and you're degrading from string to char*)

sort(word.begin(), word.end());
do{
   cout<<word;
}while(next_permutation(word.begin(), word.end());

[Chazzmundo]

i got it working before reading your reply with

int order(string word) 
{
      int len = word.length(); //length of string
      int num[len]; //how many chars there are
      int i = 0;
      cout << "\n"<<"Length of word: "<<len<<endl; 
      string temp_word = "";//to be used for checking
      int possible_combinations = factorial(len); //work out how many combinations there are
      int myints[] = {1,2,3};
      char l; //letter of int value
      
      
      for (i=0; i<len; i++) //set each char into an array
      {
        num[i] = word[i];
      }

      
      
      cout << "The " << len <<"! possible permutations gives "<< possible_combinations <<" different combinations:\n";
      
    
      cout <<"\n\n";
      sort (num,num+len);//possible_combinations);
    
      do 
      {
        for (i=0; i<len; i++) //show each character in its order
        {
            l = num[i];
            cout << l;
            temp_word += l; //add current letter to word
                        
            //check whether 
        }
        if (check(temp_word) == 1)
        {
           //cout <<"Word: "<<temp_word<<endl<<endl; //print word
           return 1;   
        }
        cout <<endl;
        temp_word = "";
      } 
      while ( next_permutation (num,num+len));//possible_combinations) );
      
      cout <<endl<< "No results found :("<<endl; //if no results are found
      return 0;
}

thank you though as your code is much neater and more efficient :)