API tools faq
paste
Advertisement
valtih1978

permutations

valtih1978
Jul 1st, 2014
294
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 11.15 KB | None | 0 0
raw download clone embed print report
  1. object permutations {
  2.  
  3.  
  4.       def withReplacements(chars: String, n: Int) {
  5.  
  6.         def internal(path: String, acc: List[String]): List[String] = {
  7.           if (path.length == n) path :: acc else
  8.             chars.toList.flatMap {c => internal(path + c, acc)}
  9.            
  10.         }
  11.        
  12.         val res = internal("", Nil)
  13.         println("there are " + res.length + " " + n + "-permutations with replacement for " + chars + " = " + res)
  14.       }                                       //> withReplacements: (chars: String, n: Int)Unit
  15.  
  16.  
  17.  
  18.       def indent[A](path: List[A]) = path map (_ => " ")
  19.                                                   //> indent: [A](path: List[A])List[String]
  20.      
  21.       def noReplacements(chars: String, n: Int/* = chars.length*/) {
  22.         //val set = chars.groupBy(c => c).map {case (c, list) => (c -> list.length)}.toList
  23.    
  24.       import scala.collection.immutable.Queue
  25.      
  26.         type Set = Queue[Char]
  27.         type Result = Queue[String]
  28.        
  29.         // The idea is that recursions will scan the set with one element excluded.
  30.         // Queue was chosen to implement the set to enable excluded element to bubble through it.
  31.         def internal(set: Set, path: String, acc: Result): Result = {
  32.           if (path.length == n) acc.enqueue(path)
  33.           else
  34.             set.foldLeft(acc, set.dequeue){case ((acc, (consumed_el, q)), e) =>
  35.              //{println(path + ": consumed " + consumed_el + ", e=" + e)}
  36.               (internal(q, consumed_el + path, acc), q.enqueue(consumed_el).dequeue)
  37.             }. _1
  38.            
  39.         }
  40.        
  41.       val set = Queue[Char](chars.toList: _*)
  42.         val res = internal(set, "", Queue.empty)
  43.         println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res)
  44.        
  45.       }                                       //> noReplacements: (chars: String, n: Int)Unit
  46.  
  47.     withReplacements("abc", 2)                    //> there are 9 2-permutations with replacement for abc = List(aa, ab, ac, ba,
  48.                                                   //| bb, bc, ca, cb, cc)
  49.     noReplacements("abc", 2)                      //> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
  50.                                                   //| a, ca, cb, ab, ac, bc)
  51.  
  52. def permute(xs:List[Int]):List[List[Int]] = xs match {
  53.   case Nil => List(List())
  54.   case head::tail => {
  55.     val tps = (0 until xs.length).map(xs.splitAt(_)).toList.filter(tp => !tp._1.contains(tp._2.head))
  56.     tps.map(tp => permute(tp._1:::tp._2.tail).map(tp._2.head :: _)).flatten
  57.   }
  58.  
  59. }                                                 //> permute: (xs: List[Int])List[List[Int]]
  60.  
  61. permute(List(1,2,3))                              //> res0: List[List[Int]] = List(List(1, 2, 3), List(1, 3, 2), List(2, 1, 3), L
  62.                                                   //| ist(2, 3, 1), List(3, 1, 2), List(3, 2, 1))
  63.  
  64.  
  65.  
  66.     withReplacements("abc", 3)                    //> there are 27 3-permutations with replacement for abc = List(aaa, aab, aac,
  67.                                                   //| aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc,
  68.                                                   //| caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
  69.     withReplacements("abc", 4)                    //> there are 81 4-permutations with replacement for abc = List(aaaa, aaab, aaa
  70.                                                   //| c, aaba, aabb, aabc, aaca, aacb, aacc, abaa, abab, abac, abba, abbb, abbc,
  71.                                                   //| abca, abcb, abcc, acaa, acab, acac, acba, acbb, acbc, acca, accb, accc, baa
  72.                                                   //| a, baab, baac, baba, babb, babc, baca, bacb, bacc, bbaa, bbab, bbac, bbba,
  73.                                                   //| bbbb, bbbc, bbca, bbcb, bbcc, bcaa, bcab, bcac, bcba, bcbb, bcbc, bcca, bcc
  74.                                                   //| b, bccc, caaa, caab, caac, caba, cabb, cabc, caca, cacb, cacc, cbaa, cbab,
  75.                                                   //| cbac, cbba, cbbb, cbbc, cbca, cbcb, cbcc, ccaa, ccab, ccac, ccba, ccbb, ccb
  76.                                                   //| c, ccca, cccb, cccc)
  77.     //noReplacements("abc", 4)
  78.  
  79. (1 to 3) foreach (u =>   noReplacements("aab", u))//> there are 3 1-permutations without replacement for Queue(a, a, b) = Queue(a
  80.                                                   //| , a, b)
  81.                                                   //| there are 6 2-permutations without replacement for Queue(a, a, b) = Queue(a
  82.                                                   //| a, ba, ba, aa, ab, ab)
  83.                                                   //| there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(b
  84.                                                   //| aa, aba, aba, baa, aab, aab)
  85.  
  86.   // With permutation implies that we have infinite supply of denominations rather than concrete coins. It is therefore
  87.   // necessary to call it with limiting length to combinations. Otherwise, generation never ends as you can always
  88.   // produce sequences of longer lengths.
  89.    // With permutaions implies that you have only one coin of every kind. The maximum length you can get is equal to the coin/kind number.
  90.    // The famous formula says perms(items, places) = items!/(items-places)! Suppose that there are more places than items -- you will get
  91.    // infinite amount of permutations, http://mathoverflow.net/questions/10124/the-factorial-of-1-2-3/137634#137634!
  92.  
  93.    // You have seen that noReplacements("aab", n) produces several combinations twice because different entries of a are
  94.    // considered as different elements. In fact we have multisets here https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
  95.    // and need to collapse the identical expressions. Using the latter algoringm, we reduce coin availalbility, every time it is picked
  96.    // and dequeue it completely only after availability drops to 0.
  97.    
  98.   noReplacements("abc", 3)                        //> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
  99.                                                   //| ba, bca, acb, cab, bac, abc)
  100.  
  101.   // Rewrite with replacement a bit to eliminate flat-map merges.
  102.    
  103.     def norep2(chars: String, n: Int/* = chars.length*/) {
  104.  
  105.     import scala.collection.immutable.Queue
  106.    
  107.       type Set = Queue[Char]
  108.       val set = Queue[Char](chars.toList: _*)
  109.  
  110.       type Result = Queue[String]
  111.      
  112.         def siblings(set: (Char, Set), offset: Int, path: String, acc: Result): Result = set match {case (bubble, queue) =>
  113.             val children = descend(queue, path + bubble, acc) // bubble was used, it is not available for children that will produce combinations in other positions
  114.             if (offset == 0) children else siblings(queue.enqueue(bubble).dequeue, offset - 1, path, children) // siblings will produce different chars at the same position, fetch next char for them
  115.         }
  116.        
  117.       def descend(set: Set, path: String, acc: Result): Result = {
  118.         if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
  119.       }
  120.      
  121.       val res = descend(set, "", Queue.empty)
  122.       println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res)
  123.      
  124.     }                                             //> norep2: (chars: String, n: Int)Unit
  125.    
  126.     assert(norep2("abc", 2) == noReplacements("abc", 2))
  127.                                                   //> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a
  128.                                                   //| b, ac, bc, ba, ca, cb)
  129.                                                   //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
  130.                                                   //| a, ca, cb, ab, ac, bc)
  131.     assert(norep2("abc", 3) == noReplacements("abc", 3))
  132.                                                   //> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a
  133.                                                   //| bc, acb, bca, bac, cab, cba)
  134.                                                   //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
  135.                                                   //| ba, bca, acb, cab, bac, abc)
  136.  
  137.    
  138.     def multisets(chars: String, n: Int/* = chars.length*/) {
  139.  
  140.       import scala.collection.immutable.Queue
  141.      
  142.       type Set = Queue[Bubble]
  143.       type Bubble = (Char, Int)
  144.       type Result = Queue[String]
  145.      
  146.         def siblings(set: (Bubble, Set), offset: Int, path: String, acc: Result): Result = set match {case ((char, avail), queue) =>
  147.             val children = descend(if (avail - 1 == 0) queue else queue.enqueue(char -> {avail-1}), path + char, acc) // childern can reuse the symbol while if it is available
  148.             if (offset == 0) children else siblings(queue.enqueue((char, avail)).dequeue, offset - 1, path, children)
  149.         }
  150.        
  151.       def descend(set: Set, path: String, acc: Result): Result = {
  152.         if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
  153.       }
  154.      
  155.       val set = Queue[Bubble]((chars.toList groupBy (c => c) map {case (k, v)  => (k, v.length)}).toList: _*)
  156.       val res = descend(set, "", Queue.empty)
  157.       println("there are " + res.length + " multiset " + n + "-permutations for " + set + " = " + res)
  158.      
  159.     }                                             //> multisets: (chars: String, n: Int)Unit
  160.  
  161.  
  162.  
  163. assert(multisets("abc", 2)  == norep2("abc", 2))  //> there are 6 multiset 2-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
  164.                                                   //| ba, bc, ac, ab, cb, ca)
  165.                                                   //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a
  166.                                                   //| b, ac, bc, ba, ca, cb)
  167. assert(multisets("abc", 3)  == norep2("abc", 3))  //> there are 6 multiset 3-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
  168.                                                   //| bac, bca, acb, abc, cba, cab)
  169.                                                   //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a
  170.                                                   //| bc, acb, bca, bac, cab, cba)
  171.  
  172. multisets("aaab", 2)                              //> there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = Queue(ba, ab,
  173.                                                   //|  aa)
  174. multisets("aab", 2)                               //> there are 3 multiset 2-permutations for Queue((b,1), (a,2)) = Queue(ba, ab,
  175.                                                   //|  aa)
  176.  
  177. multisets("aab", 3)                               //> there are 3 multiset 3-permutations for Queue((b,1), (a,2)) = Queue(baa, ab
  178.                                                   //| a, aab)
  179. norep2("aab", 3)                                  //> there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(a
  180.                                                   //| ab, aba, aba, aab, baa, baa)
  181.  
  182.  }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!