String Combinations
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: String Combinations

  1. #1
    Join Date
    May 2008
    Posts
    24

    String Combinations

    Hey All,

    I'm working on a "scrabble cheat program" ( :P ) and while I'm aware of the next_permutation function, what I really need is a "next_combination" function. Does anyone know if there is an opensource one somewhere(i tried googling) or one hidden in the standard library?

    Basically, I want a function that has input/output like this

    input: ABA

    Output:
    AAB
    ABA
    BAA
    AA
    AB
    BA
    BB
    A
    B

    input: ABC

    ABC
    ACB
    BCA
    BAC
    CBA
    CAB
    AB
    AC
    BA
    CA
    CB
    BC
    A
    B
    C

    String will be unknown length.

    I tried using recursion, but that made my head hurt pretty bad.

    Please and Thankyou,

    Johnny

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: String Combinations

    You do realize that this is going to produce an incredibly slow program, don't you?

    If you do go down this route, I'd suggest first worrying about the logic to select each subset of the available letters; rearranging them can be a separate function.

  3. #3
    Join Date
    May 2008
    Posts
    24

    Re: String Combinations

    reasonably slow, yes :P I can use somewhat fast search on my scrabble dictionary though, as it's sorted). You generally don't get more than 7 tiles in online scrabble games anyways.

    Any ideas for the logic of how to select the subsets? The rearranging could be done using the next_permutation function easy.

    Even psuedocode would be nice

  4. #4
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: String Combinations

    Well, if you don't mind doing a bit of extra work, you can easily try all 255 nontrivial subsets of 7 tiles by cycling a counter from 1 to 255, and using a bitmask to check on each increment whether bit n is 1 (and thus whether tile n should be included).

    Of course, this doesn't take into account that two tiles could be the same letter. You may be able to save a bit of effort if you figure out how to deal with that (non-trivial).

  5. #5
    Join Date
    May 2008
    Posts
    24

    Re: String Combinations

    well, in scrabble you often append it to another tile(s) so it could be larger than 7 potentionally, but the idea of using the bitmask is ideal! I can't believe I didn't think of that!

    Maybe I could have a overloaded function to support the potential problem of have say at max 11 tiles?

  6. #6
    Join Date
    May 2008
    Posts
    24

    Re: String Combinations

    Thanks Lindley, the bitfield idea works like a charm. I haven't added code yet to check for duplicates, but it runs so fast i don't know if i need to.

    I'm pretty happy with this function. I just let the library do all the work for me. Though, I'm thinking about assigning the values to all the letters and then printing them out in de-ascending order with their scores.
    Code:
    //Function checks all possible permutations of the word and looks to see if it is in the scrabble dictionary.
    //Word is the word you want to see if it's letters (rearranged) can make a valid word
    //Words is the dictionary of all the words you want to test against
    //Assumes words is sorted!
    void check_word(string word, const vector<string> &words){
      sort(word.begin(), word.end()); //Because of how next_permutation works, string must be sorted
      do{
        if(binary_search(words.begin(), words.end(), word)){
          cout << word << endl;
        }
      }
      while(next_permutation(word.begin(), word.end())); //This iterates through every permutation of the word
    }

    With this one I still need to check for duplicates. There might be a better way to do the bitmask stuff, but it takes hardly no speed (that's the only real thing I care about here).
    Code:
    //Function generates all possible subsets (except empty set) and then calls check_word to check
    // the permutation of the word.
    //If word was abc, a, b, c, ab, bc, ac, abc would all be checked by check_word.
    //Word is the word you want to see if it's letters (subsets or rearranged) can make a valid word
    //words  is the dictionary of all the words you want to test against
    void generate_subsets(string word, const vector<string> &words){
      vector<int> bitmask;
      for(int i = 0; i < word.size(); i++){
        int power = pow(2,i);
        bitmask.push_back(power);
      }
      int max_ammount = pow(2,word.size());
      long int count = 1;
      string temp = "";
      for(int i = 0; i < max_ammount; i++){
        for(int j = 0; j < bitmask.size(); j++){
          if(count & bitmask[j]){
            temp += word[j];
          }
        }
        check_word(temp, words);
        temp = "";
        count++;
      }
    }

  7. #7
    Join Date
    May 2008
    Posts
    24

    Re: String Combinations

    Hey Lindley,

    I actually found a way that can do any 7 letter word in under 5 seconds (I could shorten it by a couple of seconds it if I did a bit of pre-processing too!)

    Basically, I just count the letters a-z that each dictionary word contains and then pair the input word to the dictionary words using this method. This way, order does not matter and I only pass through the dictionary once. Even with HUGE words with hundreds of letters it only takes 10 seconds (mainly cause it takes a while to print them out).

    Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    int main(){
      fstream dictionary;                //File with scrabble dictionary in it
      vector<string> dict;               //Dictionary words loaded into here
      vector<vector<int> > dict_letters; //This is the dict words but their letters are counted instead.
    
      dictionary.open("dict.txt");
    
      if(!dictionary.is_open()){
        cout << "Error: dict.txt does not exist in directory" << endl;
        exit(-1);
      }
    
      //Put all the words from file into dict vector and dict_letters vector
      string word_buffer;
      while(!dictionary.eof()){
        dictionary >> word_buffer;
        dict.push_back(word_buffer);
    
        vector<int> letters(26,0);
        for(int i = 0; i < word_buffer.size(); i++){ //Counts letters in word
          letters[int(word_buffer[i])-97]++;
      }
        dict_letters.push_back(letters);
      }
    
      //Get word from user
      string input;
      cout << "Input your word(lowercase please): ";
      cin >> input;
      vector<int> input_letters(26,0);
      for(int i = 0; i < input.size(); i++){ //Counts letters in word
        input_letters[int(input[i])-97]++;
      }
    
    
      multimap<int, string> final_list;                                           //Pairs the found word and it's value.
      int alphabet[26] = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10}; //Used for finding the value of a word
    
      //Find words in dictionary and store the words and their values in a multimap (because it's sorted)
      for(int i = 0; i < dict_letters.size(); i++){
        bool found = true;
        for(int j = 0; j < 26; j++){
          if(dict_letters[i][j] > input_letters[j]){
            found = false;
            break;
          }
        }
        if(found){
          int value = 0;
          for(int j = 0; j < dict[i].size(); j++){ //Adds up the values of the letters
            value += alphabet[int(dict[i][j])-97];
          }
          final_list.insert(pair<int,string>(value, dict[i]));
        }
      }
    
      //Print out the words found and their values
      multimap<int, string>::iterator it;
      for (it=final_list.begin(); it != final_list.end(); it++){
        cout << (*it).first << "  " << (*it).second << endl;
      }
    
      return 0;
    }
    Who knew the best scrabble word is razzamatazzes? (if you could fit it on your board :P )
    Last edited by johnnyboldt; July 24th, 2009 at 06:15 PM. Reason: Code tags...

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center