Word Unscrambling

[mezmiro]

Hello all, I have a quandary of the algorithmic sort that I cannot wrap my head around. I'm designing a program which is meant to output all of the permutations of a scrambled word of size n. I have input with checks, and the output is very simple. I'm also using the string class.

The issue is simply in how I design this algorithm. Do you have any helpful hints/tips on how I would go about this? It seems like the number of permutations would be n!, but going from there I don't know how the loop structure would work.

This has been driving me crazy for far longer than it should.

[18hRX9L8]

What you could do is get the word and put it in an array, then switch the first letter with the next one, then the next one... until last one. then next letter, switch it with next one, then next one... then last letter just leave it. Then print them all out. For example:

user enters cta, output:

tca
act
cat

Then the user chooses the best answer (but this doesn't work for longer words, takes too long for user). Therefore, we move to files.

You save a file with the English alphabet and go through each line, getting the word switched and then scanning it with 500k words. This takes too long though. So, we split in in half. If the word is more than n characters, use the file method, otherwise, let the user do the work.

[Lynx876]

I made something similar to this the other day, a word finder.

i.e.
If I type in:

h*ll*n

It will return with:

hellene
holland
hulling

Changing out the asterisk for letters, within correct words from the English dictionary.

You could try something like the following;

-First read a dictionary file, line by line, saving each word to a <string>vector.
-Get user input.
-Loop the vector checking against length of ( user input == vector index length ).
    -If there's a match, loop the index of the string to check against correct letters.
    -If all letters match, save result to another <string>vector.

@Usandfriends, the dictionary file I use has 153223 words. And it populates the vector in 0.016 seconds. (:

[18hRX9L8]

Lynx876 wrote:

@Usandfriends, the dictionary file I use has 153223 words. And it populates the vector in 0.016 seconds. (:

Wut. ~_!

[mezmiro]

.016 seconds? Woah.. fast indeed.

So, I have some code for you guys. As jumbled as it may be, it'll probably explain the riddle buried in my head somehow. First, it's displaying too many permutations. Second, it somehow is outputting the '\0', but I told it not to! Any ideas? I want to solve the algorithm first of course before I get into parsing dictionaries.

If you can read/run it, I'm trying to move the last letter of the string(minus the '\0') left until it hits the beginning, then the next letter, etc. until all permutations are realized.

Output Function

void output()
{
     int length = in.length()-1;     //Make sure to not count the '\0'. 
     int permutations = factorial(length); //Possible permutations of the word.
     int step = 0;                         //Steps through permutations. 
     char tempR, tempL;                    //Represents the two switching chars.
     cout << "Your permutations:\n" << in << "\n"; //Make sure to output the first perm.
     while(step<=permutations)             //Makes sure we output all perms.
     {
      for(int i = length; i>=0; i--)
      {
       //There must be a more efficient way to switch letters, but I'll worry about that once it works. 
       tempR = in[i];
       tempL = in[i-1];
       in[i] = tempL;
       in[i-1] = tempR; 
       cout << in << "\n";                   //Outputs string post-modification.
      } 
      step++;
     }
}

Factorial Function

unsigned int factorial(int num)
{
    unsigned int result = 1;
    for(int i = 1; i<num; i++)
    {
      result *= (i+1);
    }
  return result;
}

[cire]

Just looking at it, it's fairly obvious that output is trying access out of the bounds of in.

in[i-1] when i == 0 ?

http://www.cplusplus.com/reference/algorithm/next_permutation/

[mezmiro]

Thanks for your help! I tried to apply this to strings, and it didn't work out so well for me.
sort() and next_permutation() don't like the arguments. Should it be cast, or is there another way to go about this?

void output()
{
     int len = in.length()-1;
     sort(in[0],in[len]);
     do 
     {
       for(int i=0; i<=len; i++)
       { cout << in[i]; }
       cout << endl; }
     while(next_permutation(in[0],in[len]));
}

Error

2545 Z:\Dev-Cpp\include\c++\3.4.2\bits\stl_algo.h instantiated from `
void std::sort(_RandomAccessIterator, _RandomAccessIterator)
 [with _RandomAccessIterator = char]' 

[Lowest0ne]

The example sort of takes for granted that you know what an iterator is. Iterators are your friend.

Most STL containers have a begin() and an end() method. std::strings have them too. These methods return iterators, one to the beginning of the container, and one to just passed the end.

Maybe the simplest example:

#include <iostream>
#include <iterator>  // Not needed for this
#include <string>

int main(void)
{
	std::string word = "Hello World";
	std::string::iterator str_iter = word.begin();
	while (str_iter != word.end())
	{
		std::cout << *str_iter <<  " ";
		str_iter++;	
	}
	std::cout << '\n';
	return 0;
 }

That being said, anytime you see a function that takes an iterator, just try to throw begin() and end() at it :). If you get a compile error, then maybe the iterator of the container is not correct for the method (ie std::sort needs a random access iterator, something that the std::list can not do. Good thing there is std::list.sort() :) ).

Iterators can act on streams too:

#include <iostream>
#include <iterator>  // Needed for this
#include <string>
#include <algorithm>

int main(void)
{
	std::string word = "This is a test of the ostream iterator";
	std::ostream_iterator<char> out_iter(std::cout, " ");
	std::copy(word.begin(), word.end(), out_iter);
	return 0;
 }

[18hRX9L8]

Hi Lynx can I please get that dictionary file??? Can you send it to me at [e-mail] ? Thanks!

[Lynx876]

I've sent you it (:

[mezmiro]

Excellent, thank you LowestOne! That helped me out a great deal. Iterators seem really powerful, and I have a feeling I'll be using them in my code a lot. :D

And now, onto the dictionary part of this program.

[newkid93]

I have a question...how do you even start to make a program?

[pogrady]

int main()
{

     return 0;
};

You'll also want to get some kind of c++ compiler :)

http://en.wikipedia.org/wiki/List_of_compilers#C.2B.2B_compilers

[18hRX9L8]

Thank you lynx! Can I send it to my friends? They also want to participate in this "challenge".

[Lynx876]

usandfriends... You have nothing to ask for... lol. I found this dictionary on a web page a while back. Do what ever you want with it! It's not mine, and there's no "You can't do this with it" lol.

What's the challenge?! I need to "re-learn" c++, I'm so rusty! ahaha. I'd be interested in challenges with people and sharing code etc, to find( learn ) more efficient code (:

Message me! Can't be hi-jacking a thread, lol.

[Lynx876]

Sh!t... lol. I just realised from my first post, that when I use the input from above, I'm getting an extra character... lol!!

i.e.
If I type in:

h*ll*n

It will return with:

hellene
holland
hulling

I'm inputting a 6 letter string and returning a 7... I thought I finished that a week ago! lol.

Edit:
Hmm, upon running the program, this problem is non-existent... But I'm not one to delete my posts... lol. So ignore the above (: ahaha