Assignment 6 finished.

[Scala.git] / Assignment_06 / src / main / scala / Anagrams.scala

diff --git a/Assignment_06/src/main/scala/Anagrams.scala b/Assignment_06/src/main/scala/Anagrams.scala
index e529124..a69b872 100644 (file)
--- a/Assignment_06/src/main/scala/Anagrams.scala
+++ b/Assignment_06/src/main/scala/Anagrams.scala
@@ -57,20 +57,64 @@ object Anagrams {
        /**
         * Generates all the subsets of a set
         */
-       def combinations(occurrences: Occurrences): List[Occurrences] = ???
-       
+       def combinations(occurrences: Occurrences): List[Occurrences] = {
+               def generator[T](x: List[List[T]]): List[List[T]] = x match {
+                       case Nil => List(Nil)
+                       case h :: t => for (j <- generator(t); i <- h) yield i :: j
+               }
+
+               def combinationsOnNumber(occurs : Occurrences) : List[Occurrences] =
+                       generator(occurs map {case (c: Char, i: Int) => (1 to i) map (j => (c, j)) toList})
+
+               val combs = for (
+                       i <- 1 to occurrences.length;
+                       l <- occurrences combinations i;
+                       l2 <- combinationsOnNumber(l)
+               ) yield l2
+
+               List() :: (combs toList)
+       }
+
        /**
         * Question 5: remove occurrences from x that are in y
         */
-       def subtract(x: Occurrences, y: Occurrences): Occurrences = ???
+       def subtract(x: Occurrences, y: Occurrences): Occurrences = {
+               def subtractMap(x: Map[Char, Int], y: Occurrences): Occurrences = y match {
+                       case Nil => x.toList
+                       case (cy, ny) :: t => {
+                               val nx = x(cy)
+                               val remaining = nx - ny
+                               if (remaining <= 0)
+                                       subtractMap(x - cy, t)
+                               else
+                                       subtractMap(x.updated(cy, remaining), t)
+                       }
+               }
+               subtractMap(x.toMap, y).sortWith((a, b) => a._1 < b._1)
+       }
        
        /**
         * Question 6 - Generate sentence anagrams
         */
        
        /** Converts a sentence into its character occurrence list. */
-       def sentenceOccurrences(s: Sentence): Occurrences = ???
+       def sentenceOccurrences(s: Sentence): Occurrences =
+    if (s.isEmpty)
+      List()
+    else
+      wordOccurrences(s.reduce(_ + _))
        
-       def sentenceAnagrams(sentence: Sentence): List[Sentence] = ???
-
+       def sentenceAnagrams(sentence: Sentence): List[Sentence] = {
+    def loop(sentence: Sentence, remaining: Occurrences) : List[Sentence] = {
+      if (remaining.isEmpty)
+        List(sentence)
+      else
+        for (
+          c <- combinations(remaining);
+          word <- dictionaryByOccurrences.applyOrElse(c, (_: Occurrences) => List());
+          s <- loop(word :: sentence, subtract(remaining, c))
+        ) yield s
+    }
+    loop(List(), sentenceOccurrences(sentence))
+       }
 }