Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wrote a simple algorithm for finding all possible letter combinations of a single word. I want to know if my code can be improved in any way, although I'm mostly interested in efficiency. You can ignore my notes if you wish, they are mostly for myself and the questions in them are not the ones I ask answers for here^^

The code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <unordered_set>

/**
    1. Used std::vector to store words, then sorted it and removed duplicates.
        >4s for 10 letters.
    2. Moved to std::unordered_set. Time improved to >2s.

    Notes:
        I used [i] instead of at(i) for efficiency in some cases (at(i) does bound checking
        (right?), and I do that myself, so it's unnecessary
        (or is the performance hit too small to matter?)).
**/

const char* outFile = "wordCombos.txt";

// Only this function should be used in main()
// Gets all possible letter combinations from a single word, prints them to a file
// Does not modify the original string
void unscramble(std::string str);

int main()
{
    // Opening the file to clear it
    std::ofstream out(outFile, std::ios::trunc);
    out.close();

    // Test values
    unscramble("aaa");
    unscramble("     Amazing \t\t\t\n  \n");
    unscramble("   \t\t\n  \n   \n \t\t");
    // This last one already takes 4 seconds. 10 letters
    // More than 3.5 million words
    unscramble("lakdjflakk");
    // 11 letters - 27 seconds
    //unscramble("lakdjlakkpp");
}

// Remove tabs, newlines, spaces
void trimSpaces(std::string& a)
{
    if(a.find_first_not_of(" \n\t") == std::string::npos){
        a = "";
        return;
    }
    int begin = a.find_first_not_of(" \n\t");
    int length = a.find_last_not_of(" \n\t") - begin + 1;
    a = a.substr(begin, length);
}

// Process a string, add all possible letter combos to word
// Assumes that a valid letters vector is given (size > 0)
// Uses recursion
void getLetterCombos(std::unordered_set<std::string>& words,
                     const std::vector<char>& letters,
                     std::string curWord)
{
    if(letters.size() == 1){
        words.insert(curWord + letters[0]);
        return;
    }

    for(int i = 0; i < letters.size(); ++i){
        std::vector<char> temp = letters;
        std::string tWord = curWord + temp[i];
        temp.erase(temp.begin() + i);
        getLetterCombos(words, temp, tWord);
    }
}

void unscramble(std::string str)
{
    trimSpaces(str);

    if(str == "" || str.find_first_of(" \t\n") != std::string::npos){
        std::cout << "Error: Invalid input: no word or more than a single word given.\n";
        return;
    }

    // All combos should be in uppercase
    std::transform(str.begin(), str.end(), str.begin(), toupper);

    std::unordered_set<std::string> words;
    std::vector<char> letters;
    letters.reserve(str.size());
    for(int i = 0; i < str.size(); ++i){
        letters.push_back(str[i]);
    }
    getLetterCombos(words, letters, "");

    std::ofstream out(outFile, std::ios::app);
    out << "Initial word: " << str << ",\nAll possible letter combinations: \n";
    for(std::unordered_set<std::string>::iterator it = words.begin(); it != words.end(); ++it){
        out << *it << "\n";
    }
    out << "\n";
}
share|improve this question
up vote 4 down vote accepted

I see some things that may help you improve your code.

Consider separating input and output

Right now, the unscramble function does both the permutation and the printing of both outputs and errors. A more modular (and likely more maintainable) approach would separate these into separate functions.

Return something useful from functions

Every single one of the routines is declared as returning void. Something is wrong there. For example, the unscramble routine could return the number of permutations or 0 on error.

Throw errors rather than printing error messages

The user of your code may be creating a GUI with no command line available and will not appreciate having your code printing instead of indicating an error to the calling code. The two ways that C++ programs generally signal an error are either by throwing an exception (if the circumstance really is exceptional) or by returning a value that indicates an error.

Eliminate global variables

Eliminating global variables allows your code to be more readable and maintainable, both of which are important characteristics of well-written code. Global variables introduce messy linkages that are difficult to spot and error prone. Either the file name or better, a std::ostream reference, should be passed rather than having the filename be a global variable. Better still, have subroutines simply operate by passing a string in or out and collect the I/O elsewhere.

Use standard algorithms

You might want to use std::next_permutation to accomplish this. It would make the code much simpler, and you're already including the required header.

share|improve this answer
    
Thank you for your response! I have a question about your fourth point, I thought global constant variables were fine? What are the actual downsides of such aproach? It seems to me that passing the file name or std::ostream reference each time I needed to write something to the file would, in fact, be a lot harder to maintain and more error-prone than having the name as a global constant, am I wrong? – Kodnot Mar 17 at 17:39
    
I can understand how you might think that. It's true that global const variables are less bad, but there is still the problem of hidden coupling. That is, the routines are dependent on that global variable, but the only way to discern that is to look through the source code. Better would be to pass a parameter, or encapsulate both the data and the functions into an object. – Edward Mar 17 at 17:47
    
I guess if I properly separate my output from my other functions as you suggested, passing a parameter won't be problematic at all. Understood and thank you!^^ – Kodnot Mar 17 at 17:53

I didn't check everything yet but here are already some remarks:

  1. Your example lacks the include of <string> so it doesn't compile this way.
    Pretty obviously a copy and paste problem ;-)
  2. Use the same types in for loops.
    Currently you are comparing int i against the size_t return value of string::size().

    e.g. for (int i = 0; i < letters.size(); ++i) should be for (size_t i = 0; i < letters.size(); ++i)

    This might not look like a big deal but it will prevent you from unwanted or undefined behaviour.
  3. The last parameter of getLetterCombos could be passed as const reference instead of copying the value on every call.
share|improve this answer
    
Thanks for your response! Actually, the lack of <string> header was not a copy-paste error, but an annoying feature of code::Blocks, the header is automatically included whenever I use std::string, so the compiler does not complain, failing to remind me to include it :D – Kodnot Mar 17 at 17:42
    
@Kodnot I don't know Code::Blocks but if this is true that's one dumb feature... – Simon Kraemer Mar 17 at 17:45
    
yup... Well, I don't know if it's a feature. It only works for certain things (i.e. if I use std::vector without the proper header, it'll complain), so it might be a bug, but it's still certainly annoying – Kodnot Mar 17 at 17:48
2  
@Kodnot Looks like this is because gcc's <iostream> makes std::string available. Found it here – Simon Kraemer Mar 17 at 18:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.