-
July 20th, 2009, 05:15 PM
#1
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
-
July 20th, 2009, 05:29 PM
#2
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.
-
July 20th, 2009, 05:38 PM
#3
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
-
July 20th, 2009, 05:44 PM
#4
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).
-
July 20th, 2009, 05:54 PM
#5
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?
-
July 21st, 2009, 12:09 PM
#6
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++;
}
}
-
July 24th, 2009, 05:14 PM
#7
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 05: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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|