Last active
March 29, 2018 05:13
-
-
Save jiamingd/02eba6f15c650e7054c86471a4e0e5e7 to your computer and use it in GitHub Desktop.
99_one
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
//http://aperiodic.net/phil/scala/s-99/, p26 | |
// In how many ways can a committee of 3 be chosen from a group of 12 people? | |
//We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). | |
//For pure mathematicians, this result may be great. But we want to really generate all the possibilities. | |
import scala.annotation.tailrec | |
val interested = Seq('a','b', 'c', 'd','e', 'f', 'g','h', 'i') | |
def combine(initS: Seq[Char]) : Seq[String] = { | |
@tailrec | |
def doCombine(sb: Seq[Char], trk: Seq[String]): Seq[String] = { | |
sb match { | |
case x :: Nil => throw (new IllegalArgumentException("Too few in seq")) | |
case x:: y :: Nil => throw (new IllegalArgumentException("Too few in seq")) | |
case a :: b :: c :: Nil => { | |
return trk | |
} | |
case h :: t => { | |
val x = t.map { c => | |
Seq(h, t.head, c).mkString | |
} | |
doCombine(t, x ++ trk) | |
} | |
} | |
} | |
doCombine(initS, Nil) | |
} | |
val r = combine(interested) |
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
import scala.annotation.tailrec | |
import scala.collection.mutable.ListBuffer | |
//What is diff: now you can specify at will how many element you need, rather than like above only for 3 char in a String | |
val interested = Seq('a','b', 'c', 'd','e', 'f', 'g','h', 'i') | |
def combine(initS: Seq[Char], groupSize: Int) : Seq[String] = { | |
@tailrec | |
def doCombine(sb: Seq[Char], grpSz: Int, trk: Seq[String]): Seq[String] = { | |
sb match { | |
case l if l.size < grpSz => throw (new IllegalArgumentException("Too few in seq")) | |
case s if s.size == grpSz => trk :+ s.mkString | |
case s => { | |
val lackOne = s.slice(0, grpSz-1) | |
var buf = new ListBuffer[String] | |
s.slice(grpSz-1, s.size).foreach{ sc => | |
buf+= (lackOne :+ sc).mkString | |
} | |
doCombine(s.tail, grpSz, trk ++ buf.toList) | |
} | |
} | |
} | |
doCombine(initS, groupSize, Nil) | |
} | |
val r = combine(interested, 4) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment