Permutations with n replacements, which generalizes permutations with replacements (replace infinitely) and without premutations (every item is available only once)

Permutations.sc

// Inspired by Oderski's anagram and the idea that SICP count change algorithm can be used
// for anagram lookup and more efficiently than odersky wanted. Anagrams are however permu
// tated "changes" and, thus, we need an algorithm for permutation. There is none in stack
// overflow, at least I could not find out whether scala and other programmers provide per
// mutations with replacements or not whereas anagrams requre special kind of permutations
// It should be that "aab", "aba" and "baa" would be permutations. Note multiplicity 2 of
// 'a'. With replacements produces aaa since a is not exhausted by two repetitions wheras
// without repetitions cannot produce sequences longer than 2 since picked two items we a
// re out of items in the dictionary. If we put two a items in the dictionary, with/wo rep
// etitions will produce idential sequences, aab and aab can be produced two times.

// The generic algorithm produced enables emulating standard permutations with/without rep
// eititions. Take multiplicity = 1 for every item and you will generate permutations with
// out repetitions. Take multiplicity exceeding the generated seq length and result will
// match the permutations with repetitions.

object Permutations {

  def printResult[A](msg: String, r: A): A = {println(msg + r) ; r}
                                                  //> printResult: [A](msg: String, r: A)A
	
  // PART I
	
  def withReplacements(chars: String, n: Int) = {
	
    def internal(path: String, acc: List[String]): List[String] = {
      if (path.length == n) path :: acc else
        chars.toList.flatMap {c => internal(path + c, acc)}
 
    }
	
    val res = internal("", Nil)
    printResult("there are " + res.length + " " + n + "-permutations with replacement for " + chars + " = ", res)
	
  }                                               //> withReplacements: (chars: String, n: Int)List[String]
	
	
  //def indent[A](path: List[A]) = path map (_ => " ")
 
  import scala.collection.immutable.Queue
	
  def noReplacements(chars: String, n: Int/* = chars.length*/) = { // unfortunately Scala cannot refer other args in the list

    type Set = Queue[Char]
    type Result = Queue[String]
 
    // The idea is that recursions will scan the set with one element excluded.
    // Queue was chosen to implement the dict to enable excluded element to bubble through it.
    def internal(dict: Set, path: String, acc: Result): Result = {
      if (path.length == n) acc.enqueue(path)
      else
        dict.foldLeft(acc, dict.dequeue){case ((acc, (consumed_el, q)), e) =>
          (internal(q, consumed_el + path, acc), q.enqueue(consumed_el).dequeue)
        }. _1
 
    }
 
    val dict = Queue[Char](chars.toList: _*)
    val res = internal(dict, "", Queue.empty)
    printResult("there are " + res.length + " " + n + "-permutations without replacement for " + dict + " = ", res)
 
  }                                               //> noReplacements: (chars: String, n: Int)Result
	
  withReplacements("abc", 2)                //> there are 9 2-permutations with replacement for abc = List(aa, ab, ac, ba, 
                                                  //| bb, bc, ca, cb, cc)
                                                  //| res0: List[String] = List(aa, ab, ac, ba, bb, bc, ca, cb, cc)
  noReplacements("abc", 2)                  //> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
                                                  //| a, ca, cb, ab, ac, bc)
                                                  //| res1: Result = Queue(ba, ca, cb, ab, ac, bc)

  //http://stackoverflow.com/a/20528637/1083704
  def permute(xs:List[Int]):List[List[Int]] = xs match {
    case Nil => List(List())
    case head::tail => {
      val tps = (0 until xs.length).map(xs.splitAt(_)).toList.filter(tp => !tp._1.contains(tp._2.head))
      tps.map(tp => permute(tp._1:::tp._2.tail).map(tp._2.head :: _)).flatten
    }
	
  }                                         //> permute: (xs: List[Int])List[List[Int]]
	
  // check function
  def ===[A](a: Seq[A], b: Seq[A]) {
    assert(a.toSet == b.toSet, a + " != " + b)
  }                                         //> === : [A](a: Seq[A], b: Seq[A])Unit
  val ref = permute(List(0,1,2))  map (_ map (i => (i + 'a') . toChar) mkString "")
                                                  //> ref  : List[String] = List(abc, acb, bac, bca, cab, cba)
  ===(ref, noReplacements("abc", 3))        //> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
                                                  //| ba, bca, acb, cab, bac, abc)

 
  withReplacements("abc", 3)                //> there are 27 3-permutations with replacement for abc = List(aaa, aab, aac, 
                                                  //| aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, 
                                                  //| caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
                                                  //| res2: List[String] = List(aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa,
                                                  //|  bab, bac, bba, bbb, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca,
                                                  //|  ccb, ccc)
  withReplacements("abc", 4)                //> there are 81 4-permutations with replacement for abc = List(aaaa, aaab, aaa
                                                  //| c, aaba, aabb, aabc, aaca, aacb, aacc, abaa, abab, abac, abba, abbb, abbc, 
                                                  //| abca, abcb, abcc, acaa, acab, acac, acba, acbb, acbc, acca, accb, accc, baa
                                                  //| a, baab, baac, baba, babb, babc, baca, bacb, bacc, bbaa, bbab, bbac, bbba, 
                                                  //| bbbb, bbbc, bbca, bbcb, bbcc, bcaa, bcab, bcac, bcba, bcbb, bcbc, bcca, bcc
                                                  //| b, bccc, caaa, caab, caac, caba, cabb, cabc, caca, cacb, cacc, cbaa, cbab, 
                                                  //| cbac, cbba, cbbb, cbbc, cbca, cbcb, cbcc, ccaa, ccab, ccac, ccba, ccbb, ccb
                                                  //| c, ccca, cccb, cccc)
                                                  //| res3: List[String] = List(aaaa, aaab, aaac, aaba, aabb, aabc, aaca, aacb, a
                                                  //| acc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, acaa, acab, acac
                                                  //| , acba, acbb, acbc, acca, accb, accc, baaa, baab, baac, baba, babb, babc, b
                                                  //| aca, bacb, bacc, bbaa, bbab, bbac, bbba, bbbb, bbbc, bbca, bbcb, bbcc, bcaa
                                                  //| , bcab, bcac, bcba, bcbb, bcbc, bcca, bccb, bccc, caaa, caab, caac, caba, c

  // Since replacements mean that we have infinite supply of denominations rather than concrete
  // coins, they can generate forever, the sequences of infinite lengths. The maximum length of
  // permutation without replacements on other hand is equal to the numebr of coins in the dictionary.
  // Dictionary length is the natural length of permutation and

  //noReplacements("abc", 4)} // throws "out of elements exception", as expected.

  // You may have notice that duplicating some coin in the dictionary, produces duplicate permutations
 
  (1 to 3) foreach (u =>   noReplacements("aab", u))
                                                  //> there are 3 1-permutations without replacement for Queue(a, a, b) = Queue(a
                                                  //| , a, b)
                                                  //| there are 6 2-permutations without replacement for Queue(a, a, b) = Queue(a
                                                  //| a, ba, ba, aa, ab, ab)
                                                  //| there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(b
                                                  //| aa, aba, aba, baa, aab, aab)
 
 
  // because different entries of a are considered as different elements. What we want in fact is to
  // have coins of multiplicity n here, aka multisets https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
  // We want coin 'a' present in two different places when we say that our dictionary is "aab".
  // Using the latter algoringm, we will reduce coin availalbility, every time it is picked.
 
 

  // 	PART II: Multiplicity
	
  def multisets(chars: String, n: Int) = { // elaborating norep to account multipicity
	
    type Set = Queue[Bubble]
    case class Bubble (val char: Char, val avail: Int)
    type Result = Queue[String]
	
    def internal(dict: Set, path: String, acc: Result): Result = {
      if (path.length == n) acc.enqueue(path)
      else {
        dict.foldLeft(acc, dict.dequeue) {
          case ((acc, (consumed_el, q)), e) => consumed_el match {
            case Bubble(char, avail) => {
	
              //children collect premutations in other positions
              val chd = if (avail == 0) acc else internal(q.enqueue(new Bubble(char, avail-1)), path + char, acc)
	
              // proceed collecting from siblings, which try different chars in the same position
              (chd, q.enqueue(consumed_el).dequeue)
            }
          }
        }. _1
      }
    }
 
    val dict = Queue[Bubble]((chars.toList groupBy (c => c) map {case (k, v)  => new Bubble(k, v.length)}).toList: _*)
    val res = internal(dict, "", Queue.empty)
    printResult("there are " + res.length + " multiset " + n + "-permutations for " + dict + " = ", res)
 
  }                                         //> multisets: (chars: String, n: Int)Result
 
  //take one element of each kind to emulate premutations without replacements
  ===(multisets("abc", 2), noReplacements("abc", 2))
                                                  //> there are 6 multiset 2-permutations for Queue(Bubble(b,1), Bubble(a,1), Bub
                                                  //| ble(c,1)) = Queue(ba, bc, ac, ab, cb, ca)
                                                  //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
                                                  //| a, ca, cb, ab, ac, bc)
  ===(multisets("abc", 3), noReplacements("abc", 3))
                                                  //> there are 6 multiset 3-permutations for Queue(Bubble(b,1), Bubble(a,1), Bub
                                                  //| ble(c,1)) = Queue(bac, bca, acb, abc, cba, cab)
                                                  //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
                                                  //| ba, bca, acb, cab, bac, abc)
	
  multisets("aab", 2)                       //> there are 3 multiset 2-permutations for Queue(Bubble(b,1), Bubble(a,2)) = Q
                                                  //| ueue(ba, ab, aa)
                                                  //| res4: Result = Queue(ba, ab, aa)
	
  multisets("aab", 3)                       //> there are 3 multiset 3-permutations for Queue(Bubble(b,1), Bubble(a,2)) = Q
                                                  //| ueue(baa, aba, aab)
                                                  //| res5: Result = Queue(baa, aba, aab)
  noReplacements("aab", 3)                  //> there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(b
                                                  //| aa, aba, aba, baa, aab, aab)
                                                  //| res6: Result = Queue(baa, aba, aba, baa, aab, aab)

  //take far more letters than resulting permutation length to emulate withReplacements
  ===(multisets("aaaaabbbbbccccc", 3), withReplacements("abc", 3))
                                                  //> there are 27 multiset 3-permutations for Queue(Bubble(b,5), Bubble(a,5), Bu
                                                  //| bble(c,5)) = Queue(bac, bab, baa, bcb, bca, bcc, bba, bbc, bbb, acb, aca, a
                                                  //| cc, aba, abc, abb, aac, aab, aaa, cba, cbc, cbb, cac, cab, caa, ccb, cca, c
                                                  //| cc)
                                                  //| there are 27 3-permutations with replacement for abc = List(aaa, aab, aac, 
                                                  //| aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, 
                                                  //| caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)

  // PART 3: For fun, foldLeft iteration over siblings is replaced by recursion
 
  def recursiveNoRepl(chars: String, n: Int) = {
 
    type Set = Queue[Char]
    val set = Queue[Char](chars.toList: _*)
 
    type Result = Queue[String]
 
    def siblings(set: (Char, Set), offset: Int, path: String, acc: Result): Result = set match {case (bubble, queue) =>
      val children = descend(queue, path + bubble, acc) // children that will produce combinations in other positions
      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
    }
 
    def descend(set: Set, path: String, acc: Result): Result = {
      if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
    }
 
    val res = descend(set, "", Queue.empty)
    printResult("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = ", res)
 
  }                                         //> recursiveNoRepl: (chars: String, n: Int)Result
	
  def recursiveMultisets(chars: String, n: Int) = {
 
    type MultiSet = Queue[Multiplicity]
    type Multiplicity = (Char, Int)
    type Result = Queue[String]
 
    def siblings(set: (Multiplicity, MultiSet), offset: Int, path: String, acc: Result): Result = set match {case ((char, avail), queue) =>
      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
      if (offset == 0) children else siblings(queue.enqueue((char, avail)).dequeue, offset - 1, path, children)
    }
 
    def descend(set: MultiSet, path: String, acc: Result): Result = {
      if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
    }
 
    val multiset = Queue[Multiplicity]((chars.toList groupBy (c => c) map {case (k, v)  => (k, v.length)}).toList: _*)
    val res = descend(multiset, "", Queue.empty)
    printResult("there are " + res.length + " multiset " + n + "-permutations for " + multiset + " = ", res)
 
  }                                         //> recursiveMultisets: (chars: String, n: Int)Result


  // PART 4: Genericized versions

  def noreplGeneric[A](chars: List[A], n: Int) = {
 
    type Set = Queue[A]
    val set = Queue[A](chars.toList: _*)
 
    type Result = List[List[A]]
 
    def siblings(set: (A, Set), offset: Int, path: List[A], acc: Result): Result = set match {case (bubble, queue) =>
      val children = descend(queue, bubble :: path, acc) // bubble was used, it is not available for children that will produce combinations in other positions
      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
    }
 
    def descend(set: Set, path: List[A], acc: Result): Result = {
      if (path.length == n) path :: acc else siblings(set.dequeue, set.size-1, path, acc)
    }
 
    val res = descend(set, List.empty, List.empty)
    printResult("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = ", res)
 
  }                                         //> noreplGeneric: [A](chars: List[A], n: Int)Result
	
  ===(noreplGeneric("aab".toList, 2).map(_ mkString ""), noReplacements("aab", 2))
                                                  //> there are 6 2-permutations without replacement for Queue(a, a, b) = List(Li
                                                  //| st(a, b), List(a, b), List(a, a), List(b, a), List(b, a), List(a, a))
                                                  //| there are 6 2-permutations without replacement for Queue(a, a, b) = Queue(a
                                                  //| a, ba, ba, aa, ab, ab)
 
  // generic multisets
  def genericPermutation[A](chars: List[A], n: Int) = {
 
    type Multiset = Queue[Multiplicity]
    type Multiplicity = (A, Int)
    type Result = List[List[A]]
 
    def siblings(set: (Multiplicity, Multiset), offset: Int, path: List[A], acc: Result): Result = set match {case ((char, avail), queue) =>
      val children = descend(if (avail - 1 == 0) queue else queue.enqueue(char -> {avail-1}), char :: path, acc) // childern can reuse the symbol while if it is available
      if (offset == 0) children else siblings(queue.enqueue((char, avail)).dequeue, offset - 1, path, children)
    }
 
    def descend(set: Multiset, path: List[A], acc: Result): Result = {
      if (path.length == n) path :: acc else siblings(set.dequeue, set.size-1, path, acc)
    }
 
    val multiset = Queue[Multiplicity]((chars.toList groupBy (c => c) map {case (k, v)  => (k, v.length)}).toList: _*)
    val res = descend(multiset, List.empty, List.empty)
    printResult("there are " + res.length + " multiset " + n + "-permutations for " + multiset + " = ", res)
 
  }                                         //> genericPermutation: [A](chars: List[A], n: Int)Result

  def sgp(dict: String, len: Int) = genericPermutation(dict.toList, len) map (_ mkString "")
                                                  //> sgp: (dict: String, len: Int)List[String]
  === (sgp("aaab", 2), multisets("aaab", 2))//> there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = List(List(a,
                                                  //|  a), List(b, a), List(a, b))
                                                  //| there are 3 multiset 2-permutations for Queue(Bubble(b,1), Bubble(a,3)) = 
                                                  //| Queue(ba, ab, aa)

 
 
  //take one letter of each to emulate withoutReplacements
  ===(sgp("aaaaabbbbbccccc", 2), withReplacements("abc", 2))
                                                  //> there are 9 multiset 2-permutations for Queue((b,5), (a,5), (c,5)) = List(
                                                  //| List(c, c), List(a, c), List(b, c), List(a, a), List(b, a), List(c, a), Li
                                                  //| st(b, b), List(c, b), List(a, b))
                                                  //| there are 9 2-permutations with replacement for abc = List(aa, ab, ac, ba,
                                                  //|  bb, bc, ca, cb, cc)
  ===(sgp("aaaaabbbbbccccc", 3), withReplacements("abc", 3))
                                                  //> there are 27 multiset 3-permutations for Queue((b,5), (a,5), (c,5)) = List
                                                  //| (List(c, c, c), List(a, c, c), List(b, c, c), List(a, a, c), List(b, a, c)
                                                  //| , List(c, a, c), List(b, b, c), List(c, b, c), List(a, b, c), List(a, a, a
                                                  //| ), List(b, a, a), List(c, a, a), List(b, b, a), List(c, b, a), List(a, b, 
                                                  //| a), List(c, c, a), List(a, c, a), List(b, c, a), List(b, b, b), List(c, b,
                                                  //|  b), List(a, b, b), List(c, c, b), List(a, c, b), List(b, c, b), List(a, a
                                                  //| , b), List(b, a, b), List(c, a, b))
                                                  //| there are 27 3-permutations with replacement for abc = List(aaa, aab, aac,
                                                  //|  aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc
                                                  //| , caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
  ===(sgp("abc", 2), noReplacements("abc", 2))
                                                  //> there are 6 multiset 2-permutations for Queue((b,1), (a,1), (c,1)) = List(
                                                  //| List(a, c), List(b, c), List(b, a), List(c, a), List(c, b), List(a, b))
                                                  //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(
                                                  //| ba, ca, cb, ab, ac, bc)
  ===(sgp("abc", 3), noReplacements("abc", 3))
                                                  //> there are 6 multiset 3-permutations for Queue((b,1), (a,1), (c,1)) = List(
                                                  //| List(b, a, c), List(a, b, c), List(c, b, a), List(b, c, a), List(a, c, b),
                                                  //|  List(c, a, b))
                                                  //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(
                                                  //| cba, bca, acb, cab, bac, abc)


  // Published at https://gist.github.com/valtih1978/99d8b320e59fcde634ad

}