4 * Sentence anagrams generation
5 * MSE course, T-AdvPrPa course
12 type Occurrences
= List
[(Char
, Int
)]
13 type Sentence
= List
[Word
]
16 * The dictionary is simply a sequence of words.
17 * It is predefined and obtained as a sequence using the utility method `loadDictionary`.
19 val dictionary
: List
[Word
] = loadDictionary()
22 * Question 1 : converts the word into its character occurrence list.
25 * wordOccurences("abcd") gives List(('a', 1), ('b', 1), ('c', 1), ('d', 1))
26 * wordOccurences("aabcddd") gives List(('a', 2), ('b', 1), ('c', 1), ('d', 3))
28 * Note: the upper case and lower case version of the character are treated as the
29 * same character, and are represented as a lower case character in the occurrence list.
30 * The list is sorted alphabeticaly.
32 def wordOccurrences(w
: Word
): Occurrences
=
33 w
.toLowerCase().groupBy(identity
).toList
.map
{ case (_
, letters
) => (letters(0), letters
.length
) }.sortWith((a
, b
) => a
._1
< b
._1
)
36 * Question 2: Valid words
38 * The `dictionaryByOccurrences` is a `Map` from different occurrences to a sequence of all
39 * the words that have that occurrence count. This map serves as an easy way to obtain all the anagrams of a word given its occurrence list.
41 lazy val dictionaryByOccurrences
: Map
[Occurrences
, List
[Word
]] =
42 dictionary
groupBy (w
=> wordOccurrences(w
))
45 * Question 3: Returns all the anagrams of a given word
47 def wordAnagrams(word
: Word
): List
[Word
] =
48 dictionaryByOccurrences get
wordOccurrences(word
) match {
49 case Some(words
) => words
54 * Question 4: Returns all the subsets of an occurrence list
58 * Generates all the subsets of a set
60 def combinations(occurrences
: Occurrences
): List
[Occurrences
] = {
61 def generator
[T
](x
: List
[List
[T
]]): List
[List
[T
]] = x
match {
63 case h
:: t
=> for (j
<- generator(t
); i
<- h
) yield i
:: j
66 def combinationsOnNumber(occurs
: Occurrences
) : List
[Occurrences
] =
67 generator(occurs map
{case (c
: Char
, i
: Int
) => (1 to i
) map (j
=> (c
, j
)) toList
})
70 i
<- 1 to occurrences
.length
;
71 l
<- occurrences combinations i
; // Combination on letters.
72 l2
<- combinationsOnNumber(l
) // Combination on numbers
75 List() :: (combs toList
)
79 * Question 5: remove occurrences from x that are in y
81 def subtract(x
: Occurrences
, y
: Occurrences
): Occurrences
= {
82 def subtractMap(x
: Map
[Char
, Int
], y
: Occurrences
): Occurrences
= y
match {
84 case (cy
, ny
) :: t
=> {
86 val remaining
= nx
- ny
88 subtractMap(x
- cy
, t
)
90 subtractMap(x
.updated(cy
, remaining
), t
)
93 subtractMap(x
.toMap
, y
).sortWith((a
, b
) => a
._1
< b
._1
)
97 * Question 6 - Generate sentence anagrams
100 /** Converts a sentence into its character occurrence list. */
101 def sentenceOccurrences(s
: Sentence
): Occurrences
=
105 wordOccurrences(s
.reduce(_
+ _
))
107 def sentenceAnagrams(sentence
: Sentence
): List
[Sentence
] = {
108 def loop(sentence
: Sentence
, remaining
: Occurrences
) : List
[Sentence
] = {
109 if (remaining
.isEmpty
)
113 c
<- combinations(remaining
);
114 word
<- dictionaryByOccurrences
.applyOrElse(c
, (_
: Occurrences
) => List());
115 s
<- loop(word
:: sentence
, subtract(remaining
, c
))
118 loop(List(), sentenceOccurrences(sentence
))