Last active
May 14, 2020 20:27
-
-
Save vdebergue/5a5cb077ca78348b4acc3a229947a3fd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
object Combs extends App { | |
/* | |
findAndPrint(7, 2) | |
findAndPrint(14, 3) | |
findAndPrint(11, 2) | |
findAndPrint(41, 8) | |
findAndPrint(41, 8) | |
*/ | |
// 1 | |
findAndPrint(10, 3, Set(4, 9)) | |
//findAndPrint(17, 2) | |
findAndPrint(15, 4, Set(8, 9, 4, 3), Set(2)) | |
// findAndPrint(11, 2, Set(1, 2, 9)) | |
findAndPrint(10, 3, Set(8, 9, 4)) | |
findAndPrint(19, 4, Set(8, 9), Set(7, 4)) | |
println("******* 2 ******") | |
findAndPrint(24, 4, Set(3, 1, 2), Set(4,6)) | |
findAndPrint(23, 5) | |
findAndPrint(15, 2) | |
findAndPrint(15, 3, Set(7, 8), Set()) | |
findAndPrint(18, 4, Set(5), Set(7)) | |
findAndPrint(13, 3, Set(7)) | |
findAndPrint(19, 3, Set(5, 7), Set(9)) | |
println("******* 3 ******") | |
findAndPrint(18, 3, Set(9, 4, 1, 2), Set(5)) | |
findAndPrint(14, 4, Set(9, 4, 7)) | |
findAndPrint(11, 3, Set(5)) | |
findAndPrint(28, 6, Set(), Set(3, 8, 1)) | |
findAndPrint(23, 4, Set(8)) | |
// findAndPrint(22, 4, Set(8, 1, 6)) | |
// findAndPrint(8, 2, Set(3, 7)) | |
def possibles(target: Int, size: Int): Set[Set[Int]] = { | |
val combs = combinaisons(size) | |
combs.filter(_.sum == target) | |
} | |
def findAndPrint( | |
target: Int, | |
size: Int, | |
exclusions: Set[Int] = Set.empty, | |
inclusions: Set[Int] = Set.empty | |
) = { | |
val res = possibles(target, size) | |
val res2 = res | |
.filter(s => s.intersect(exclusions).isEmpty) | |
.filter(s => s.intersect(inclusions) == inclusions) | |
val str = res2.map(_.toSeq.sorted.mkString(", ")).mkString("\n ") | |
println( | |
s"""Combinations for $target with $size numbers without $exclusions and containing $inclusions: | |
| $str | |
|""".stripMargin | |
) | |
res | |
} | |
def combinaisons(k: Int, n: Int = 9): Set[Set[Int]] = { | |
if (k > n) Set.empty | |
else if (k == n) Set((1 to n).toSet) | |
else if (k == 1) (1 to n).map(x => Set.apply(x)).toSet | |
else { | |
val combs = combinaisons(k - 1, n - 1) | |
combinaisons(k, n - 1) union (combs.map(_ union Set(n))) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment