From 9cd519633e0e5357ecfe1b6021b6aa905285a021 Mon Sep 17 00:00:00 2001 From: Ummon Date: Mon, 27 Apr 2015 01:13:04 +0200 Subject: [PATCH] Assignment 6 finished. --- Assignment_06/Assignment_06.ipr | 6 + Assignment_06/Assignment_06.iws | 339 ++++++++++++++---- Assignment_06/src/main/scala/Anagrams.scala | 56 ++- .../src/test/scala/AnagramsTests.scala | 24 ++ notes.txt | 1 + 5 files changed, 345 insertions(+), 81 deletions(-) diff --git a/Assignment_06/Assignment_06.ipr b/Assignment_06/Assignment_06.ipr index 2b43590..215f3af 100644 --- a/Assignment_06/Assignment_06.ipr +++ b/Assignment_06/Assignment_06.ipr @@ -28,6 +28,12 @@ + + + diff --git a/Assignment_06/Assignment_06.iws b/Assignment_06/Assignment_06.iws index a87b850..2b43238 100644 --- a/Assignment_06/Assignment_06.iws +++ b/Assignment_06/Assignment_06.iws @@ -2,8 +2,11 @@ - - + + + + + @@ -31,8 +34,40 @@ - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + @@ -57,6 +92,7 @@ @@ -69,10 +105,9 @@ - @@ -137,6 +172,28 @@ @@ -255,22 +316,9 @@ + - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + @@ -332,6 +401,17 @@ + + + + + + + + + @@ -467,16 +554,18 @@ - - - - + + + + + - - - - + + + + + @@ -529,41 +618,45 @@ - + + + + + - - + - + - + + - + - + + - + - + + - - - + - @@ -578,8 +671,29 @@ - - + + + + file://$PROJECT_DIR$/src/test/scala/AnagramsTests.scala + 158 + + + + file://$PROJECT_DIR$/src/main/scala/Anagrams.scala + 108 + + + + + + + + + + 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)) + } } diff --git a/Assignment_06/src/test/scala/AnagramsTests.scala b/Assignment_06/src/test/scala/AnagramsTests.scala index 6efda03..3824b09 100644 --- a/Assignment_06/src/test/scala/AnagramsTests.scala +++ b/Assignment_06/src/test/scala/AnagramsTests.scala @@ -79,6 +79,30 @@ class AnagramsTests extends FunSuite { List(('a', 2), ('b', 2))) assert(combinations(abba).toSet === abbacomb.toSet) } + + test("combinations: \"abbac\"") { + val abbac = List(('a', 2), ('b', 2), ('c', 1)) + val abbaccomb = List( + List(), + List(('a', 1)), + List(('a', 2)), + List(('b', 1)), + List(('c', 1)), + List(('a', 1), ('b', 1)), + List(('a', 2), ('b', 1)), + List(('b', 2)), + List(('a', 1), ('b', 2)), + List(('a', 2), ('b', 2)), + List(('a', 1), ('c', 1)), + List(('a', 2), ('c', 1)), + List(('b', 1), ('c', 1)), + List(('b', 2), ('c', 1)), + List(('a', 1), ('b', 1), ('c', 1)), + List(('a', 2), ('b', 1), ('c', 1)), + List(('a', 1), ('b', 2), ('c', 1)), + List(('a', 2), ('b', 2), ('c', 1))) + assert(combinations(abbac).toSet === abbaccomb.toSet) + } /** * Test suite for question 5 diff --git a/notes.txt b/notes.txt index e69de29..08dc930 100644 --- a/notes.txt +++ b/notes.txt @@ -0,0 +1 @@ +Examen: vendredi 19 juin à 9h00 \ No newline at end of file -- 2.43.0