How to use single letters to form words

Question

Hey I currently have this code. It gets the user to input strings into an array, with a limit of 5. I plan to use the array to then form words from the array. How can I achieve this?

    const int row = 5;
    char array[row];
    char count = 0;
    char letter;
    while (count < 5)
    {
        cout << "Enter a letter: ";
        cin >> letter;
        array[count] = letter;
        count++;
    }
    cout << "Letter inputed" << endl;
    for (count = 0; count < 5; count++)
    {
        cout << array[count] << " " <<  endl;
    }
    system("pause");

Answer 1

Here's a hint to get you started on the right track: don't even consider using std::next_permutation unless this is something you'll only ever use once or twice (and probably not even then, because it's actually more complicated than doing the job right).

Using std::next_permutation, your function will be approximately N! times slower than necessary¹ -- in the case of 5 letters, that'll be 120 times slower, and if you ever use longer words, it'll get worse very quickly (e.g., for 10 letters it's over 3.5 million).

Instead, start by pre-processing your dictionary. Instead of a std::set<std::string> of words, create an std::map<std::string, std::vector<string>> (or std::unordered_map, though English has few enough words that this probably won't make a huge difference). As you read in a word from the dictionary, create a sorted version of that string. Use that as the key, and push the original version of the word onto the vector for that key.

Then when you get a word from the user, sort it, look that up in the map, and the associated vector will contain every word (from your dictionary) that can be created from those letters.

---

_{1. If you use std::map instead of std::unordered_map, that should be something like N!/(log N), but N! grows so fast and log N grows so slowly that it the difference is negligible (if you get N large enough that log N = 3, N! will be so large that N!/log N computation steps...well, you start to get into questions of cosmology, like whether the universe will have died of heat death before then (to which the answer seems to be "yes, probably").}

Answer 2

Here's a hint to get you started. There's a function in the standard library called std::next_permutation. Assuming you have a dictionary of words to check against, a possible solution could look like this:

std::sort(array, array + row);
do {
    // Check if array is a word.
} while (std::next_permutation(array, array + row));

This will cycle through every permutation of letters. It's now up to you to verify that it is a valid word.

Answer 3

This solution uses an associative array to map from sorted letters of the word to the words having such sorted letters. It's thus possible to get an answer with one lookup in the map, which takes asymptotically O(log N) time, where N is a size of your dictionary.

Create a file named dic.txt. In case you're using Visual Studio it should be in the same directory as your *.cpp files. Put several words inside in a "word in a row" format. Try the following code:

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

int main() {
    // Dictionary file is in a "word in a row" format
    map< string, vector<string> > dictionary;
    ifstream dictionary_file("dic.txt");
    if (!dictionary_file.good()) {
        cout << "File doesn't exist" << endl;
        return 0;
    }
    string word;
    while (dictionary_file >> word) {
        string key = word;
        sort(key.begin(), key.end());
        dictionary[key].push_back(word);
    }

    // Read the letters
    string letters;
    cin >> letters;
    if (letters.size() > 5) {
        cout << "Too much letters" << endl;
        return 0;
    }

    // Sort the letters
    sort(letters.begin(), letters.end());

    // Output the answers
    vector<string> & ret = dictionary[letters];
    for (size_t i = 0, ilen = ret.size(); i < ilen; ++i) {
        cout << ret[i] << endl;
    }
}

Mention that such a solution cares for a case your letters are in. In case you don't need it, you can add calls to strtolower function (got that name from PHP) before you add a word to your dictionary and before you sort your letters.

string strtolowers(string const & word) {
    string ret = word;
    transform(ret.begin(), ret.end(), ret.begin(), tolower);
    return ret;
}

You'll need to add <cctype> header for this function to work.