Advertisement
Guest User

Untitled

a guest
Mar 18th, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 3.88 KB | None | 0 0
  1. import scala.annotation.tailrec
  2.  
  3. /**
  4.   * Created by runnerpeople on 18.03.2017.
  5.   */
  6.  
  7. class Permutation private(k : Int, m: Int, list_args : List[(Int,Int)]) {
  8.     if (m > k) {
  9.        throw new IllegalArgumentException("Number of elements must be greater than range of elements!")
  10.     }
  11.  
  12.     val list = list_args match {
  13.         case Nil  => List((k,m))
  14.         case _    => list_args
  15.     }
  16.  
  17.     def this(k : Int, m: Int) = this(k,m,Nil)
  18.     def this(list_args: List[(Int,Int)]) = this(0,0,list_args)
  19.  
  20.  
  21.     def + (p : Permutation): Permutation = {
  22.         val flag = (list.head._1 >= p.list.head._1) && (list.head._2 < p.list.head._2)
  23.         val whole_list_x = flag match {
  24.             case false => (this.list ::: p.list).sortWith(Permutation.sortTupleByFirst)
  25.             case true  => (p.list ::: this.list).sortWith(Permutation.sortTupleByFirst)
  26.         }
  27.         // Functions help to find tuples (t11,t12) > (t21,t22), where t11>t21 && t12>t22              //
  28.         def inner(xs : List[(Int,Int)],elem: (Int,Int),flag : Boolean): Boolean = {
  29.             (xs,elem,flag) match {
  30.               case (Nil,element,result)                          => result
  31.               case (x :: tail,element,result) if x._2 < elem._2  => inner(tail,element,result)
  32.               case (x :: tail,element,result)                    => inner(tail,element,!result)
  33.             }
  34.         }
  35.         def inner_help(xs: List[(Int,Int)],result : List[(Int,Int)]): List[(Int,Int)] = {
  36.             val flag = false
  37.             (xs,result) match {
  38.                 case (Nil,result_list)                             => result_list
  39.                 case (x :: tail,result_list) if inner(tail,x,flag) => inner_help(tail,x :: result_list)
  40.                 case (x :: tail,result_list)                       => inner_help(tail,result_list)
  41.             }
  42.         }
  43.         // =============================================================================              //
  44.         val elements_delete = inner_help(whole_list_x.reverse,Nil)
  45.         val right_list = whole_list_x.filter(elem => !elements_delete.contains(elem))
  46.         new Permutation(right_list)
  47.     }
  48.  
  49.     def in_: (seq : List[Int]) = {
  50.       if (seq.length != seq.distinct.length)
  51.           throw new IllegalArgumentException("Finding permutations with repetition " +
  52.                                              "in set of permutations with no repetition!")
  53.       val list = this.list
  54.       val new_list = list.filter(pair => pair._1 >= seq.max && pair._2 == seq.length)
  55.       new_list.nonEmpty
  56.     }
  57.  
  58.  
  59.     def size () = {
  60.       @tailrec
  61.       def inner(xs : List[(Int,Int)], accum : BigInt): BigInt = {
  62.         xs match {
  63.           case x :: tail => inner(tail, accum + Permutation.count(x._1,x._2))
  64.           case Nil => accum
  65.         }
  66.       }
  67.       inner(this.list,BigInt(0))
  68.     }
  69.  
  70. }
  71.  
  72. object Permutation {
  73.     def sortTupleByFirst(v1 : (Int,Int), v2: (Int,Int)) = {
  74.         v1._1 >= v2._1
  75.     }
  76.  
  77.     def count(k: Int, m: Int): BigInt = {
  78.       if (k == m)
  79.         factorial(k+1)
  80.       else
  81.         factorial(k + 1) / factorial(k + 1 - m)
  82.     }
  83.  
  84.     def factorial(n: Int): BigInt = {
  85.       @tailrec
  86.       def inner(number : Int, accum : BigInt): BigInt = {
  87.         number match {
  88.           case 1 => accum
  89.           case _ => inner(number-1, accum * number)
  90.         }
  91.       }
  92.        inner(n,BigInt(1))
  93.     }
  94.   // Generated by Intellij IDEA          //
  95.   def main(args: Array[String]): Unit = {
  96.     val p1 = new Permutation(15,2)
  97.     val p2 = new Permutation(9,4)
  98.     val p3 = new Permutation(4,3)
  99.     p1 + p2 + p3
  100.     println(p1.size())
  101.     println(List(3,1) in_: p3)
  102.   }
  103.   // ================================    //
  104. }
  105.  
  106. // Run in REPL //
  107.  
  108. //val p1 = new Permutation(15,2)
  109. //val p2 = new Permutation(9,4)
  110. //val p3 = new Permutation(4,3)
  111. //p1 + p2 + p3
  112. //println(p1.size())
  113. //println(List(3,1) in_: p3)
  114.  
  115. // ========== //
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement