Trying to finish my unscrambling project

[iSWATxJOKERi]

Hi, I am doing the project ideas that I found on the forum for people wanting to get better at C++ ( http://www.cplusplus.com/forum/beginner/3473/) and I am stuck on number 11. Perform 4-letter WORD UNSCRAMBLING i.e. List all possible combinations of 4-letters in a word. Ex: The word 'TEST' can be unscrambled as TEST,TETS,TSET,TSTE,TTSE,TTES,etc. (Beginner)... I got the code to work but when I enter a word that has repeating letters such as BOOT or BUTTER or PROFESSOR, the program compiles but doesn't print anything and keeps running. When input any other word with unique-letters like STOP or BASKET or SPECT, it runs and prints all possible combinations of the word.

Here's my code:

#include <iostream>
#include <vector>
#include <map>
#include <ctime>
#include <algorithm>

using namespace std;

int permutation(int);
void unscramble(string);

int main()
{
	//do {
	//unscramble function
	//} while ();
	//permutation(3);
	unscramble("STOP");
	return 0;
}

void unscramble(string four)
{
	int wlength = four.length();
	int amount = permutation(wlength);
	//creates a vector and the for loop adds each character to an index
	vector<char> letters(wlength);
	for (int j = 0; j < wlength; j++)
	{
		letters[j] = four[j];
	}
	//counter for the size of vector holding all the unique arrangements of the word
	int counts;
	counts = 0;
	vector<string> listOfWords(amount);
	//the string that holds each new unscrambled word
	string newnew;
	//unscrambles the word and adds it to the array
	do
	{
		//shuffles the letters vector
	LOOP:random_shuffle(letters.begin(), letters.end());
		//iterates through the 'letters' vector and adds each char to the newnew string
		for (vector<char>::iterator it = letters.begin(); it != letters.end(); ++it)
		{
			newnew += *it;
		}
		//if new word is in vector, go to beginning, else add to vector
		if (find(listOfWords.begin(), listOfWords.end(), newnew) != listOfWords.end())
		{
			newnew.erase(newnew.begin(), newnew.end());
			goto LOOP;
		}
		else
		{
			listOfWords.push_back(newnew);
			newnew.erase(newnew.begin(), newnew.end());
			counts += 1;
		}
	} while (counts < amount);
	//prints out vector of all possible combinations of a word
	for (int k = 0; k < listOfWords.size(); k++)
		cout << listOfWords[k] << endl;

}

//returns how many unique ways word of x length can be rearranged

int permutation(int len)
{
	int answer = 1;
	for (int i = len; i > 0; i--)
	{
		answer *= i;
	}
	return answer;
}

[Duthomhas]

It is a fairly subtle logic flaw. Consider the input string "ABB". This can have 3×2×1 = 6 possible permutations:

  ABB
  ABB
  BAB
  BBA
  BAB
  BBA

See how this is a problem? I had to use [u]underlining[/u] to tell the ‘B’s apart. Your code cannot terminate because it cannot get past a list of:

  ABB
  BAB
  BBA

...which is three short of your desired six.

There are two ways you can resolve this.


BTW, on line 56 you use push_back(), but on line 35 you initialize the vector with all the space it needs. I recommend changing line 35 and keeping the push_back().


BTW2, using a random shuffle is an interesting (and valid!) way to create the permutations, but you can do so much better.


BTW3, please don’t use goto where a simple continue will suffice.


Hope this helps.

[iSWATxJOKERi]

See how this is a problem? I had to use underlining to tell the ‘B’s apart. Your code cannot terminate because it cannot get past a list of:

ABB
BAB
BBA

...which is three short of your desired six.

Thanks, yeah I can see the flaw there.

BTW2, using a random shuffle is an interesting (and valid!) way to create the permutations, but you can do so much better.

Yeah, that's the logic that I came up with in my head and at first I was using the rand generator but that didn't work and I learned about the random shuffle. I'm still learning c++ so I don't know how I can do much better :p.

BTW3, please don’t use goto where a simple continue will suffice.

OK, I looked it up and I see why. Thanks :).


I am going to see how to fix the logical flaw now. :3

[Duthomhas]

Remember, there are two possibilities (at least, off the top of my head) that you have for fixing it. The first involves counting. The second involves getting rid of that PRNG. :O)

[iSWATxJOKERi]

OMG :p, I think I just fixed it. You and the internet are a lifesaver!

Remember, there are two possibilities (at least, off the top of my head) that you have for fixing it. The first involves counting. The second involves getting rid of that PRNG. :O)

I had to think reaaal hard about the logical flaw, and finally,I figured why not make the permutation formula consider repition of letters which is the permutation of n!/how many letters repeat.

#include <iostream>
#include <vector>
#include <map>
#include <ctime>
#include <algorithm>

using namespace std;

int permutation(int, int);
void unscramble(string);

int main()
{
	//do {
	//unscramble function
	//} while ();
	//permutation(3);
	unscramble("FOOD");
	return 0;
}

void unscramble(string wordOfChoice)
{
	int wlength = wordOfChoice.length();
	int amount = permutation(wlength,2);
	//creates a vector and the for loop adds each character to an index
	vector<char> letters(wlength);
	for (int j = 0; j < wlength; j++)
	{
		letters[j] = wordOfChoice[j];
	}
	//counter for the size of vector holding all the unique arrangements of the word
	int counts;
	counts = 0;
	vector<string> listOfWords;
	//the string that holds each new unscrambled word
	string newnew;
	//unscrambles the word and adds it to the array
	do
	{
		//shuffles the letters vector
	random_shuffle(letters.begin(), letters.end());
		//iterates through the 'letters' vector and adds each char to the newnew string
		for (vector<char>::iterator it = letters.begin(); it != letters.end(); ++it)
		{
			newnew += *it;
		}
		//if new word is in vector, go to beginning of loop, else add to vector
		if (find(listOfWords.begin(), listOfWords.end(), newnew) != listOfWords.end())
		{
			newnew.erase(newnew.begin(), newnew.end());
			continue;
		}
		else
		{
			listOfWords.push_back(newnew);
			newnew.erase(newnew.begin(), newnew.end());
			counts += 1;
		}
	} while (counts < amount);
	//prints out vector of all possible combinations of a word
	for (int k = 0; k < listOfWords.size(); k++)
		cout << listOfWords[k] << endl;

}

//returns how many unique ways word of x length can be rearranged

int permutation(int len,int lenn)
{
	//len = length of word
	//lenn = how many times a letter repeats more than once
	int an;
	int answer = 1;
	for (int i = len; i > 0; i--)
	{
		answer *= i;
	}
	an = answer / lenn;

	return an;
}

Right now, I am hard coding the parameters for permutation but i'll fix it later so the user can input the length of the word and how many different words and how many times they repeat. For example if more than one letter repeat like MISSISSIPPI.
Thanks alot! :)

[Duthomhas]

Does my heart good. :O)

[dhayden]

I think you can simplify the code by making letters a string instead of a vector<char>.
Then you don't need newnew.

#include <iostream>
#include <vector>
#include <map>
#include <ctime>
#include <algorithm>

using namespace std;

int permutation(int, int);
void unscramble(string);

int
main()
{
    //do {
    //unscramble function
    //} while ();
    //permutation(3);
    unscramble("FOOD");
    return 0;
}

void
unscramble(string wordOfChoice)
{
    int amount = permutation(wordOfChoice.size(), 2);
    //the string that holds each new unscrambled word
    //unscrambles the word and adds it to the array
    string letters(wordOfChoice);
    //counter for the size of vector holding all the unique
    //arrangements of the word
    int counts;
    counts = 0;
    vector < string > listOfWords;

    do {
	//shuffles the letters vector
	random_shuffle(letters.begin(), letters.end());
	//if new word is in vector, go to beginning
	//of loop, else add to vector
	if (find(listOfWords.begin(), listOfWords.end(), letters) == listOfWords.end()) {
	    listOfWords.push_back(letters);
	    counts += 1;
	}
    } while (counts < amount);
    //prints out vector of all possible combinations of a word
    for (unsigned k = 0; k < listOfWords.size(); k++)
	cout << listOfWords[k] << endl;

}

//returns how many unique ways word of x length can be rearranged

int
permutation(int len, int lenn)
{
    //len = length of word
    //lenn = how many times a letter repeats more than once
    int an;
    int answer = 1;
    for (int i = len; i > 0; i--) {
	answer *= i;
    }
    an = answer / lenn;

    return an;
}

But your solution is fundamentally inefficient. If you run it with a larger word, it will get slower and slower as it takes more and more guesses to stumble across all the permutations. Can you think of a way to generate all of the permutations directly? Have you learned about recursion? With recursion it's trivial.

[iSWATxJOKERi]

I think you can simplify the code by making letters a string instead of a vector<char>.
Then you don't need newnew.

Yes, I can see that now.

But your solution is fundamentally inefficient. If you run it with a larger word, it will get slower and slower as it takes more and more guesses to stumble across all the permutations. Can you think of a way to generate all of the permutations directly? Have you learned about recursion? With recursion it's trivial.

:D Hahaha yeah I just learned it today *facepalm*. I went on to the next project and I need to use recursion to do it and I realized I could've used recursion to solve this permutation problem much more efficiently. Thanks !

[Niccolo]

:D Hahaha yeah I just learned it today *facepalm*. I went on to the next project and I need to use recursion to do it and I realized I could've used recursion to solve this permutation problem much more efficiently. Thanks!

That is a very common situation to find yourself in.

It has happened to high level scientists and engineers deep into their careers. In some cases of history, research work taking months or years went by when the very moment you describe happens, instantly invalidating all that time!

I'll tell you this, though...the harder you facepalm your forehead (below that threshold that knocks you unconscious), the more likely you'll never forget the solution ;)