String Combinations

[johnnyboldt]

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

[Lindley]

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.

[johnnyboldt]

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

[Lindley]

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).

[johnnyboldt]

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?

[johnnyboldt]

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.

//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).

//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++;
  }
}

[johnnyboldt]

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).

#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 )