X-Git-Url: http://git.euphorik.ch/?p=Scala.git;a=blobdiff_plain;f=Assignment_06%2Fsrc%2Fmain%2Fscala%2FAnagrams.scala;fp=Assignment_06%2Fsrc%2Fmain%2Fscala%2FAnagrams.scala;h=a69b8729c92b7ffff5e56171c695a4f0dd754b0f;hp=e52912447851b71ad2ecc792504fa3f7472f3abb;hb=9cd519633e0e5357ecfe1b6021b6aa905285a021;hpb=6c413508bbba63f2421fd57d87eba4266c5beca0

diff --git a/Assignment_06/src/main/scala/Anagrams.scala b/Assignment_06/src/main/scala/Anagrams.scala
index e529124..a69b872 100644
--- 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))
+	}
 }