/* This file is part of cardwords
(c) 1998 1999 2000 Tobias Peters
see file COPYING for the copyright terms.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
// cardwords_charcombination.hh
#ifndef CARDWORDS_CHARCOMBINATION_HH
#define CARDWORDS_CHARCOMBINATION_HH
/* The purpose of class CardWords_CharCombination:
When it comes to search for possible words to lay with a
fixed length of characters, we have a certain pool of N characters
from which to choose and we know how many of them we need (Z).
We then want to iterate over all possible combinations of Z
characters chosen from those N characters.
The class defined in this file will iterate through all possible
combinations for us. When created (constructor), we have to tell it
about the pool of possible characters (this is done in the form of
a const CardWords_String &). It is not necessary to tell how long the
combinations should be, the CardWords_CharCombinations object will
calculate all combinations from length 1 to pool.length(). This is
different from the previous implementation and saves recalculation
for every single table position.
After the creation there are CardWords_CharCombination[i].size()
combinations with length (i+1). They are not CardWords_Strings, but
only hash_keys of type hashing_type, because thats all we need. they
are accessible through CardWords_CharCombinations[i][j] whith
0 <= j <= CardWords_CharCombination[i].size().
If there are many wildcards (many may also be 2 or even 1), it may be that
calculating possible combinations is an unnecessary overhead.
Consider there are 5,000 - 10,000 words with length 5,6,7, contained in a
hash table in as many buckets or less. Consider there are 2 Wildcards,
each of the wildcard can take N meanings. They can form
\sum_{n=1}^N{n} or N(N+1)/2 different combinations. For a german charset
(N=30) that's 465 combinations only for the wildcards. Then, for a
5-letter-word, we also need 3 from the remaining 5 non-wildcard cards.
That's another 10 combinations. Together we have about 4,000 combinations
to check. That's not far from the total number of words we have in the
dictionary at all.
It might be better, not to calculate combinations (and store them!), but to
search every word in the dictionary and test if it fits.
At the moment, I am uncertain where to place the border, at 2 or 3
wildcards, or even 1? A generic aproach seems to be the best to me now.
Nothing of this is implemented yet.
*/
#include "cardwords_string.hh"
#include "cardwords_exceptions.hh"
#include
#include
#include
namespace CardWords {
template
class CharCombination : public vector< vector< hashing_type > >
{
public:
// This constructor is for Cards without wildcards:
CharCombination ( const String & possibleChars);
// This constructor is for Cards with wildcards:
CharCombination ( const String & possibleChars,
// w/o wildcards
size_t no_of_wildcards);
private:
// combinate is for initialisation and directly called from the constructor.
// It is a recursive (and cascading) function and needs to know about how
// deep the recursion has gone already. This is done in this way:
//
// combinate gets a param size_t length_so_far. That's the length of the
// combination that the calling function generated. It is at the same time
// the index of the parent class vector where this instance has to store its
// calculated combinations of length length_so_far+1. Another param is
// size_t next_usable_index. This is the index of the first Char
// in sorted_pool that this instance of combinate is allowed to use.
void
combinate (const hashing_type & combination_so_far,
size_t length_so_far,
size_t next_usable_index,
const String & sorted_pool);
// the number of available chars:
const size_t noAvail;
};
}
#include "cardwords_charcombination.icc"
#endif