This might be a good time to use recursion:
Set<String> getCartesianProduct(List<String> originalWords, TreeMap<String, Set<String>> wordVariationSet) {
Set<String> resultSet =new HashSet<String>(); // to store answer
varyWord(resultSet, "", originalWords, wordVariationSet, 0); // begin recursion with empty sentence
return resultSet; // return result
}
void varyWord(Set<String> result, String sentence, List<String> originalWords, Map<String, Set<String>> wordVariationSet, int index) {
if (index==originalWords.size()) { // no more words to vary -> sentence is complete
result.add(sentence); // add to results
return; // done (return from recursion)
}
if (index>0) sentence += " "; // add a space if working on any but first word
String theOriginalWord = originalWords.get(index); // grab original word
varyWord(result, sentence + theOriginalWord, originalWords, wordVariationSet, index+1); // add to sentence and vary next word
Set<String> wordVariations = wordVariationSet.get(theOriginalWord); // grab variations of this word
if (wordVariations!=null) // make sure they're not null
for(String word: wordVariations) // iterate over variations
varyWord(result, sentence + word, originalWords, wordVariationSet, index+1); // add to sentence and vary next word
}
I hope this code is self-explanatory. If not, let me know and I can add some detail.
A couple of things to note:
- You wrote "I used treeMap to preserve the sequence of words.", but unfortunately a treemap sorts its keys by their natural ordering (in this case by alphabet), not by when they were added. That's why I included the
List<String> originalWords
as a parameter, which does preserve ordering. So, you will need to initialize that as well (make anArrayList
and right after youput(...)
a word intoaMapOfSet
, alsoadd(...)
it to the list). - This code is missing a couple of checks, like a null-check for
originalWords
andwordVariationSet
, a check whetherwordVariationSet
contains the same words asoriginalWords
, ... - If your
originalWords
-sentence contains the same word twice, thewordVariationSet
will not be able to handle different variations for each. Instead, your secondput(...)
will overwrite your first one.