permutations combinations and co / published by https://github.com/dacr/code-examples-manager #cf93c83d-4fbb-4f46-86c5-4ebbe5e10f6b/d2a6622daf69bc61f679deee9576c3519f8fb63

math-combs-perms-and-co.sc

// summary : permutations combinations and co
// keywords : scala, math, combinations, permutations, cheatsheet, @testable
// publish : gist
// authors : David Crosson
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// id : cf93c83d-4fbb-4f46-86c5-4ebbe5e10f6b
// created-on : 2020-12-14T05:51:15Z
// managed-by : https://github.com/dacr/code-examples-manager
// run-with : scala-cli $file

// ---------------------
//> using scala "3.4.2"
//> using dep "org.scalatest::scalatest:3.2.16"
//> using objectWrapper
// ---------------------
import org.scalatest._,flatspec._,matchers._
import scala.math._

def fact(num: Int): BigInt = {
  LazyList
    .from(1)
    .take(num)
    .map(x => BigInt(x))
    .foldLeft(BigInt(1)) {case (a,b) => a * b}
}


def permutationsWithRepetitions[T](input : List[T], n : Int) : List[List[T]] = {
  if (n==1) for {el <- input} yield List(el)
  else for {
    in <- input
    perm <- permutationsWithRepetitions(input, n - 1)
  } yield in :: perm
}


class CombPermTest extends AnyFlatSpec with should.Matchers {
  override def suiteName: String = "FactTest"

  "combinations" should "give the number combinations of size k in a set of size n (the order doesn't matter)" in {
    info("count = n!/(k!(n-k)!)")
    info("""In English we use the word "combination" loosely, without thinking if the order of things is important.""")
    info("When the order doesn't matter, it is a combination")
    info("When the order does matter it is a permutation")
    "ABC".toSeq.combinations(2).mkString(",") shouldBe "AB,AC,BC"
    "ABCD".toSeq.combinations(3).mkString(",") shouldBe "ABC,ABD,ACD,BCD"
    "ABCDEF".toSeq.combinations(3).size shouldBe fact(6)/(fact(6-3)*fact(3))
  }

  "combinations of all sizes (without taking into account the order)" should "" in {
    info("of course with the empty set")
    "ABC".to(Set).subsets().map(_.mkString).mkString(",") shouldBe ",A,B,C,AB,AC,BC,ABC"
    // TODO - TO BE CONTINUED
  }

  "permutations without repetition" should "give all the possible rearrangement of the elements of a set (the order matter)" in {
    info("count = n!")
    "AB".toSeq.permutations.mkString(",") shouldBe "AB,BA"
    "ABC".toSeq.permutations.mkString(",") shouldBe "ABC,ACB,BAC,BCA,CAB,CBA"
    "ABCDEF".toSeq.permutations.size shouldBe fact(6)
  }

  "permutations with repetition" should "" in {
    val in = "ABC".to(List)
    val perms = permutationsWithRepetitions(in, 2)
    perms.map(_.mkString).mkString(",") shouldBe "AA,AB,AC,BA,BB,BC,CA,CB,CC"
    perms.size shouldBe pow(in.size, 2)
  }

}

org.scalatest.tools.Runner.main(Array("-oDF", "-s", classOf[CombPermTest].getName))