Anagram Solver/ Word jumbler

[jpotts]

Hi,
I am working on a Word Jumble, which will hopefully be turned into an anagram solver. I just have two questions. If i have the user input a string such as "apple" how do i have it split it into 5 different letters and jumble them into a different order. Secondly is how do i jumble the letters? I have read the page on the Next Permutation command, but it didnt make any sense to me. Can anyone explain how to use it or give me a different method.
Thanks
Joel

[hamsterman]

Strings are character arrays. You get nth char with mystring[n]. Same works when mystring is an std::string.

To shuffle, use the method here: http://en.wikipedia.org/wiki/Fisher–Yates_shuffle or a function (implemented the same way) random_shuffle from <algorithm> header.

[jpotts]

could you please provide a simple example of it? also could you please help with the sort command too? Im using the h.file <algorithm> but i use sort and it says that sort is not defined in this scope.

#include <iostream>
#include <algorithm>

int main()
{ 
	int list[] = {2,5,1,3,4};
	
	
	sort (list);
	
	std::cout << list;
	return 0;
}

[hamsterman]

sort (like random_shuffle and most other functions in <algorithm> ) takes two arguments. One is an iterator (pointer) to the first element of your container (array) and the other is an iterator (pointer) to one element past the last element of your container (array). So the arguments you'd put them in your example are sort( list, list+5 );.

[jpotts]

I still have the error, that sort is not declared in this scope, when i try to compile it...

[jpotts]

I have changed my code to this

#include <iostream>
#include <algorithm>

int main()
{ 
	int list[] = {2,5,1,3,4};
	
	
	std::sort (list, list+5);
	
	std::cout << list;
	return 0;
}

(i added the std:: infront of sort)

and now i dont get an error, but my output is this

0xbfc83b0c

[hamsterman]

Now your printing the address of the memory where your array begins. To print the elements, you need a for loop.

[jpotts]

what would i need the parameters to be for the for loop?

[wolfgang]

Okay I wrote out some of this to get an idea how to explain the method.
You need to have a swap function and a function for the scrambling:

void swap (char &a, char &b);
std::string str_scramble (const std::string &old_str);

Basically, get two random numbers from 0 to str.length().
Then swap their positions in an array or std::string.
Repeat as many times as you want (which means you'll need a counter as well to stop the loop, as well as constantly generate new random numbers).
Print scrambled word or store it for later use.

The loop should just run for a number of times. I suggest a multiple of the length of the word. Maybe 200 loops for each letter.

[jpotts]

so i should have it swap random letters in my string so many times, that all the possibilities will be there?

[hamsterman]

The for loop would be for( int i = 0; i < 5; i++ ) cout << list[i];

As for the algorithm, swapping random values is the point, though if you did as my link suggested, you'd only need N swaps. There is pseudocode, so you shouldn't have any problems writing it..

[jpotts]

Thankyou :)

The code i have so far is this:

#include <ctime>

int main()
{ 
 srand ( time(NULL) );

 int x = rand() % 4+1;
 int y = rand() % 4+1;
 std::string myString = "sony";
 std::cout << "myString is " << myString.length() << " characters long\n";

 swap (myString[0], myString[3]);
 std::cout << myString << endl;
}

Im working on an online compiler, because im not using my own comp, but i plan on making x & y the 2 places that i swap in the word, and i plan on replacing the word with something that the user inputs. I also plan on making a for loop that will print out the new jumbled word (and eventually have it read a file and check to see if any of the new jumbles are a word to make it an anagram solver) :)

Ill let you know how it goes!
Joel

[jpotts]

Hey,
everything is going well, except i ran into a little problem with an if statement:

#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>

int main()
{ 
 srand ( time(NULL) );
 
	std::string myString;	
	std::cin >> myString;	// input your word
	int length = myString.length(); //used to find permutations line16
	int fact = 1; // number of permutations
	int arrayNum = 0; // used to know what array slot to use line24
	
	 while (length > 1) //finds the number of permutations possible
{
 fact = fact*length;
 length--;
 std::cout << fact << "\n";
}

	std::string array[fact];
	array[arrayNum] = myString;
	arrayNum ++; // so the next input will be a different slot
	
	while (arrayNum < fact)
	{
	std::swap (myString[rand() % myString.length()], myString[rand() % myString.length()]);
		if (myString != array[1] && myString != array[2] && myString != array[3] && myString != array[4] && myString != array[5])
		{
		array[arrayNum] = myString;
		arrayNum++;
		}
		else 
		continue;
	}
	
	int elements = sizeof(array) / sizeof(array[0]); 	// outputs array
	for (int i = 0; i < elements; ++i)					
	std::cout << array[i] << " ";						
		

}

line 30 is supposed to make it so that it wont be able to put the same string into a new slot, however when i run i still get repeats... any advice?

[hamsterman]

On line 30 you're forgetting that arrays start from 0. Also, you should be using a for loop for this. You don't know whether you'll have 6 elements in array.

Also, std::string array[fact]; is not legal in C++. Using a variable for the size of a static array was fine in C. Some C++ compilers allow it, some don't. You should be using std::string* array = new std::string[fact];. Don't forget to delete it later.

[jpotts]

I understand what i have done wrong with the if function, thanks. Could you please explain how

std::string* array = new std::string[fact];

works? What is the astrix for after the first string? Is it saying make a new string "array" that equals a new string that is an array?
Thankyou
Joel

[jpotts]

Two things. With the

std::string* array = new std::string[fact];

it isnt adding anything new to the array. also is there a way to check the entire array for 1 thing, instead of searching each individual element?

[hamsterman]

That * means a pointer. If you haven't learned them yet, I guess it's fine if you go back to the variable length array..
As for searching, instead of the usual for loop, you could http://www.cplusplus.com/reference/algorithm/find/

[jpotts]

Hey,
I have a couple of chapters to read before i get to pointers in the C++ book i have. I got my code to work up to 4 letters, but i think that the code just takes to long when i get to 5 or more...

#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>

int main()
{ 
 srand ( time(NULL) );
 
	std::string myString;	
	std::cin >> myString;	// input your word
	int length = myString.length(); //used to find permutations line16
	int fact = 1; // number of permutations
	int arrayNum = 0; // used to know what array slot to use line24
	int checkRepeat;
	int counter;
	
	 while (length > 1) //finds the number of permutations possible
{
 fact = fact*length;
 length--;
 std::cout << fact << "\n";
}

	std::string array[fact];
	array[arrayNum] = myString;
	arrayNum ++; // so the next input will be a different slot
	
	while (arrayNum < fact)
	{
		checkRepeat = 0;
	std::swap (myString[rand() % myString.length()], myString[rand() % myString.length()]);
	
		for (counter = 0; counter < fact; counter++)
		{
			if (myString == array[counter])// counter increases so it checks until counter = fact
			{
			checkRepeat++; // used to know if there is a repeat
			}
		}
		
	if (checkRepeat < 1) // if checkRepeat is less than 1 then no repeats
		{
		array[arrayNum] = myString;
		arrayNum++;
		}
	}
	
	
	int elements = sizeof(array) / sizeof(array[0]); 	// outputs array
	for (int i = 0; i < elements; ++i)					
	std::cout << array[i] << " ";	
	
	return 0;					
		

}

its kind of a spaghetti code at the moment, but i tried to put in comments so you could understand. when i learn more about pointers, ill try using the find fuction you showed me. :)

[hamsterman]

This is a bad idea. You aren't searching for permutations, you're just shuffling and expecting to find them all. This could take forever. There are better methods to find all permutations of a set.
See http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
If you don't want to write this yourself, even though it shouldn't be hard, use http://www.cplusplus.com/reference/algorithm/next_permutation/

[creekist]

The random shuffling method isn't really a good idea. I wrote an anagram solver once that worked pretty fast.

Essentially you read the acceptable words into an array, and the shuffled words into another array.

Then what you do is check if the length of the shuffled word is the same as one word from the list.

If so, then check if all the character are present, you do this by reading the shuffled word character into a vector, and for each match you delete said character from the vector.

Then at the end you check if the vector is empty.

When I tested it out it worked.

:)