How to resolve the algorithm Find the missing permutation step by step in the Scala programming language

Published on 12 May 2024 09:40 PM
#Scala

How to resolve the algorithm Find the missing permutation step by step in the Scala programming language

Table of Contents

Problem Statement

Listed above are   all-but-one   of the permutations of the symbols   A,   B,   C,   and   D,   except   for one permutation that's   not   listed.

Find that missing permutation.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Find the missing permutation step by step in the Scala programming language

Source code in the scala programming language

def fat(n: Int) = (2 to n).foldLeft(1)(_*_)
def perm[A](x: Int, a: Seq[A]): Seq[A] = if (x == 0) a else {
  val n = a.size
  val fatN1 = fat(n - 1)
  val fatN = fatN1 * n
  val p = x / fatN1 % fatN
  val (before, Seq(el, after @ _*)) = a splitAt p
  el +: perm(x % fatN1, before ++ after)
}
def findMissingPerm(start: String, perms: Array[String]): String = {
  for {
    i <- 0 until fat(start.size)
    p = perm(i, start).mkString
  } if (!perms.contains(p)) return p
  ""
}
val perms = """ABCD
CABD
ACDB
DACB
BCDA
ACBD
ADCB
CDAB
DABC
BCAD
CADB
CDBA
CBAD
ABDC
ADBC
BDCA
DCBA
BACD
BADC
BDAC
CBDA
DBCA
DCAB""".stripMargin.split("\n")
println(findMissingPerm(perms(0), perms))


println("missing perms: "+("ABCD".permutations.toSet
  --"ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB".stripMargin.split(" ").toSet))

You may also check:How to resolve the algorithm Primality by Wilson's theorem step by step in the Miranda programming language
You may also check:How to resolve the algorithm Runtime evaluation step by step in the Oforth programming language
You may also check:How to resolve the algorithm Bitwise operations step by step in the PL/I programming language
You may also check:How to resolve the algorithm Case-sensitivity of identifiers step by step in the Java programming language
You may also check:How to resolve the algorithm Knuth shuffle step by step in the AppleScript programming language