Scrabble letter search! ideas

[mrronoah]

So i want to make a program where i put in x amount of letters and it print out all of the possibilities. I'm sure that it is possible somehow but i am a beginner and would like some ideas. Has someone done anything like this before? I think i would have to import a dictionary of words and have it search through, would they all be in one array or separate variables?

I know what i want but i don't know how to achieve it.
Any advice or ideas are greatly appreciated.

[JLBorges]

> but i am a beginner and would like some ideas.

Start with a simple, brute force algorithm:

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

std::vector<std::string> possible_words( const std::string& letters,
                                            const std::vector<std::string>& dict )
{
    std::vector<std::string> result ;

    for( const std::string& word : dict ) // for each word in the dictionary
    {
        if( letters.size() >= word.size() ) // if we have enough letters
        {
            std::string avail = letters ; // available letters
            bool found_all_letters = true ;

            for( char c : word ) // for each letter in word
            {
                // try to find the letter c in available letters
                auto pos = avail.find(c) ;
                if( pos == std::string::npos ) // not there, can't form this word
                {
                    found_all_letters = false ;
                    break ;
                }
                else avail.erase( pos, 1 ) ; // remove this letter from available letters
            }

            if( found_all_letters ) result.push_back(word) ; // add it to the result
        }
    }

    return result ;
}

int main()
{
    std::string letters = "aabcdeeffgik" ;
    std::vector<std::string> dict = { "apple", "bed", "bead", "geek", "dew", "fed", "feed" } ;
    auto words = possible_words( letters, dict ) ;
    for( const auto& w : words ) std::cout << w << '\n' ;
}

Once you are past the beginner stage, you might want to represent the dictionary as a trie (prefix tree) http://en.wikipedia.org/wiki/Trie
Or better still, as a patricia trie (radix tree) http://en.wikipedia.org/wiki/Radix_tree

[mrronoah]

Thanks a lot! i am still a beginner so this is a little bit over my head but im starting to understand how its working. :)

[JLBorges]

The algorithm itself is very straightforward.

What is 'a little bit over my head'? std::vector<> and std::string?

Those are two things that you should learn early rather than late.
http://www.mochima.com/tutorials/vectors.html
http://www.mochima.com/tutorials/strings.html