Código para enumerar permutaciones en Scala

Question

He codificado una función para enumerar todas las permutaciones de una lista determinada. ¿Qué piensas del código a continuación?

def interleave(x:Int, l:List[Int]):List[List[Int]] = { 
    l match { 
    case Nil => List(List(x)) 
    case (head::tail) => 
     (x :: head :: tail) :: interleave(x, tail).map(head :: _) 
    } 
} 

def permutations(l:List[Int]):List[List[Int]] = { 
    l match { 
    case Nil => List(List()) 
    case (head::tail) => 
     for(p0 <- permutations(tail); p1 <- interleave(head, p0)) yield p1 
    } 
} 

Answer 1

Dado un Seq, uno ya puede tener permutaciones invocando el método permutations.

scala> List(1,2,3).permutations.mkString("\n") 
res3: String = 
List(1, 2, 3) 
List(1, 3, 2) 
List(2, 1, 3) 
List(2, 3, 1) 
List(3, 1, 2) 
List(3, 2, 1) 

Además también hay un método para combinations:

scala> List(1,2,3).combinations(2).mkString("\n") 
res4: String = 
List(1, 2) 
List(1, 3) 
List(2, 3) 

En cuanto a su aplicación, diría tres cosas:

(1) Su bien parecido

(2) Proporcionar un iterador (que es el enfoque de colecciones estándar que permite descartar elementos). De lo contrario, ¡puedes obtener listas con 1000! elementos que pueden no caber en la memoria.

scala> val longList = List((1 to 1000):_*) 
longList: List[Int] = List(1, 2, 3,... 


scala> permutations(longList) 
java.lang.OutOfMemoryError: Java heap space 
    at scala.collection.immutable.List.$colon$colon(List.scala:67) 
    at .interleave(<console>:11) 
    at .interleave(<console>:11) 
    at .interleave(<console>:11) 

(3) Debe eliminar permutaciones duplicados (según lo observado por Luigi), ya que:

scala> permutations(List(1,1,3)) 
res4: List[List[Int]] = List(List(1, 1, 3), List(1, 1, 3), List(1, 3, 1), List(1, 3, 1), List(3, 1, 1), List(3, 1, 1)) 

scala> List(1,1,3).permutations.toList 
res5: List[List[Int]] = List(List(1, 1, 3), List(1, 3, 1), List(3, 1, 1)) 

Answer 2

creo que esa función ya existe en la biblioteca estándar: Seq.permutations. Entonces, ¿por qué reinventar la rueda otra vez?

Answer 3

en cuenta la diferencia en este caso: la versión

scala> permutations(List(1,1,2)) foreach println 
List(1, 1, 2) 
List(1, 1, 2) 
List(1, 2, 1) 
List(1, 2, 1) 
List(2, 1, 1) 
List(2, 1, 1) 

La versión de referencia:

scala> List(1,1,2).permutations foreach println 
List(1, 1, 2) 
List(1, 2, 1) 
List(2, 1, 1) 

Answer 4

I Supongo que estás practicando tu habilidad de programación de Scala. Aquí hay otro, donde la idea es tomar diferentes elementos como cabeza de secuencia y las repeticiones se eliminan a través del filter. La complejidad del código estará bien, ya que O (n) + O (n o quizás n^2) + O (n) * P (n-1) está dominado por O (n) * P (n-1), donde P (n) es el número de permutación y no se puede mejorar,.

def permute(xs:List[Int]):List[List[Int]] = xs match { 
    case Nil => List(List()) 
    case head::tail => { 
    val len = xs.length 
    val tps = (0 to len-1).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 
    } 
} 

Answer 5

Tal vez este hilo es ya bien saturado, pero yo pensé en tirar mi solución en la mezcla:

Suponiendo que no hay elementos de repetición:

def permList(l: List[Int]): List[List[Int]] = l match { 
    case List(ele) => List(List(ele)) 
    case list => 
    for { 
     i <- List.range(0, list.length) 
     p <- permList(list.slice(0, i) ++ list.slice(i + 1, list.length)) 
    } yield list(i) :: p 
} 

Con elementos de repetición, evitando duplicados (no tan bonitos):

def permList(l: List[Int]): List[List[Int]] = l match { 
    case List(ele) => List(List(ele)) 
    case list => 
    for { 
     i <- List.range(0, list.length) 
     val traversedList = list.slice(0, i) 
     val nextEle = list(i) 
     if !(traversedList contains nextEle) 
     p <- permList(traversedList ++ list.slice(i + 1, list.length)) 
    } yield list(i) :: p 
} 

Es posible que no sea el más "list-y", dado que usa slice y un índice en la lista, pero es bastante conciso y una forma ligeramente diferente de verlo. Funciona identificando cada elemento en la lista y calculando las permutaciones de lo que queda, y luego concatenando el elemento individual con cada una de esas permutaciones. Si hay una forma más idiomática de hacer esto, me encantaría saberlo.

Answer 6

creo que la solución de la mina es mejor que otros

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) 
     println("there are " + res.length + " " + n + "-permutations with replacement for " + chars + " = " + res) 
     }          //> withReplacements: (chars: String, n: Int)Unit 




     def noReplacements(chars: String, n: Int) { 
     //val set = chars.groupBy(c => c).map {case (c, list) => (c -> list.length)}.toList 

     import scala.collection.immutable.Queue 

     type Set = Queue[Char] 
     val set = Queue[Char](chars.toList: _*) 

     type Result = Queue[String] 

     // The idea is that recursions will scan the set with one element excluded. 
     // Queue was chosen to implement the set to enable excluded element to bubble through it. 
     def internal(set: Set, path: String, acc: Result): Result = { 
      if (path.length == n) acc.enqueue(path) 
      else 
      set.foldLeft(acc, set.dequeue){case ((acc, (consumed_el, q)), e) => 
       (internal(q, consumed_el + path, acc), q.enqueue(consumed_el).dequeue) 
      }. _1 

     } 

     val res = internal(set, "", Queue.empty) 
     println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res) 

     }          //> noReplacements: (chars: String, n: Int)Unit 



    withReplacements("abc", 2)     //> there are 9 2-permutations with replacement for abc = 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) 


    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) 
    // you can run with replacements (3 chars, n = 4) but noReplacements will fail for obvious reason -- you cannont combine 3 chars to produce 4 
    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) 
(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) 

Estos son los mismos 3 líneas de código, pero las longitudes de permutación variables son compatibles y de la lista concatenaciones son eliminados.

He hecho que el segundo sea más ideomático (de modo que se eviten las fusiones de acumulador planas de acumulador, lo que también lo hace más recursivo) y extendido en permutaciones multiset, para que pueda decir que "aab", "aba "y" baa "son permutaciones (entre sí). La idea es que la letra "a" es reemplazable dos veces en lugar infinita (con el caso de reemplazo) o disponible una sola vez (sin reemplazos). Por lo tanto, necesita un contador, que le indica cuántas veces puede encontrar cada carta para reemplazarla.

// Rewrite with replacement a bit to eliminate flat-map merges. 

    def norep2(chars: String, n: Int/* = chars.length*/) { 

    import scala.collection.immutable.Queue 

     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) // 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: 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) 
     println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res) 

    }            //> norep2: (chars: String, n: Int)Unit 

    assert(norep2("abc", 2) == noReplacements("abc", 2)) 
                //> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a 
                //| b, ac, bc, ba, ca, cb) 
                //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b 
                //| a, ca, cb, ab, ac, bc) 
    assert(norep2("abc", 3) == noReplacements("abc", 3)) 
                //> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a 
                //| bc, acb, bca, bac, cab, cba) 
                //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c 
                //| ba, bca, acb, cab, bac, abc) 


    def multisets(chars: String, n: Int/* = chars.length*/) { 

     import scala.collection.immutable.Queue 

     type Set = Queue[Bubble] 
     type Bubble = (Char, Int) 
     type Result = Queue[String] 

     def siblings(set: (Bubble, Set), 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: Set, path: String, acc: Result): Result = { 
     if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc) 
     } 

     val set = Queue[Bubble]((chars.toList groupBy (c => c) map {case (k, v) => (k, v.length)}).toList: _*) 
     val res = descend(set, "", Queue.empty) 
     println("there are " + res.length + " multiset " + n + "-permutations for " + set + " = " + res) 

    }            //> multisets: (chars: String, n: Int)Unit 



assert(multisets("abc", 2) == norep2("abc", 2)) //> there are 6 multiset 2-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
                //| ba, bc, ac, ab, cb, ca) 
                //| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a 
                //| b, ac, bc, ba, ca, cb) 
assert(multisets("abc", 3) == norep2("abc", 3)) //> there are 6 multiset 3-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
                //| bac, bca, acb, abc, cba, cab) 
                //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a 
                //| bc, acb, bca, bac, cab, cba) 

assert (multisets("aaab", 2) == multisets2("aaab".toList, 2)) 
                //> there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = Queue(ba, ab, 
                //| aa) 
                //| there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = List(List(a, 
                //| a), List(b, a), List(a, b)) 
multisets("aab", 2)        //> there are 3 multiset 2-permutations for Queue((b,1), (a,2)) = Queue(ba, ab, 
                //| aa) 

multisets("aab", 3)        //> there are 3 multiset 3-permutations for Queue((b,1), (a,2)) = Queue(baa, ab 
                //| a, aab) 
norep2("aab", 3)         //> there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(a 
                //| ab, aba, aba, aab, baa, baa) 

Como generalización, puede obtener con/sin reemplazos utilizando la función multisec. Por ejemplo,

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


//take one letter of each to emulate withoutReplacements 
assert(multisets("aaaaabbbbbccccc", 3) == noReplacements("abc", 3)) 
                //> there are 27 multiset 3-permutations for Queue((b,5), (a,5), (c,5)) = Queue 
                //| (bac, bab, baa, bcb, bca, bcc, bba, bbc, bbb, acb, aca, acc, aba, abc, abb, 
                //| aac, aab, aaa, cba, cbc, cbb, cac, cab, caa, ccb, cca, ccc) 
                //| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c 
                //| ba, bca, acb, cab, bac, abc) 

If you are more interested about permutations, you may look at

Answer 7

Aquí es una versión basada en span.

def perms[T](xs: List[T]): List[List[T]] = xs match { 
    case List(_) => List(xs) 
    case _ => for (x <- xs 
       ; val (l, r) = xs span { x!= } 
       ; ys <- perms(l ++ r.tail) 
       ) yield x :: ys 
} 

Answer 8

def permutator[T](list: List[T]): List[List[T]] = { 

    def _p(total: Int, list: List[T]): List[List[T]] = { 
    if (total == 0) { 
     // End of the recursion tree 
     list.map(List(_)) 
    } else { 
     // Controlled combinatorial 
     // explosion while total > 0   
     for (i <- list; 
      j <- _p(total - 1, list)) 
     yield { i :: j } 

     // It is a recursion tree to generate the 
     // permutations of the elements 
     // -------------------------------------- 
     // total = 0 => _p returns 3 elements (A, B, C) 
     // total = 1 => _p returns 3 * 3 List(List(A, A)... 
     // total = 2 => _p returns 3 * 3 * 3 elements List(List(A, A, A)... 

    } 
    } 

    _p(list.length - 1, list) 
} 

permutator(List("A", "B", "C")) 

// output: 
List(A, A, A),List(A, A, B),List(A, A, C),List(A, B, A),List(A, B, B), 
List(A, B, C),List(A, C, A),List(A, C, B),List(A, C, C),List(B, A, A), 
List(B, A, B),List(B, A, C),List(B, B, A),List(B, B, B),List(B, B, C), 
List(B, C, A),List(B, C, B),List(B, C, C),List(C, A, A),List(C, A, B), 
List(C, A, C),List(C, B, A),List(C, B, B),List(C, B, C),List(C, C, A), 
List(C, C, B),List(C, C, C) 

Answer 9

Esta es una aplicación que se basa en el concepto de ciclo y una aplicación trivial de permute con dos elementos. No maneja duplicados y aspecto desbordamiento de pila en el método permute

object ImmuPermute extends App { 
    def nextCycle(nums: List[Int]): List[Int] = { 
    nums match { 
     case Nil => Nil 
     case head :: tail => tail :+ head 
    } 
    } 
    def cycles(nums: List[Int]): List[List[Int]] = { 
    def loop(l: List[Int], acc: List[List[Int]]): List[List[Int]] = { 
     if (acc.size == nums.size) 
     acc 
     else { 
     val next = nextCycle(l) 
     loop(next, next :: acc) 
     } 
    } 
    loop(nums, List(nums)) 
    } 
    def permute(nums: List[Int]): List[List[Int]] = { 
    nums match { 
     case Nil => Nil 
     case head :: Nil => List(List(head)) 
     case first :: second :: Nil => List(List(first, second), List(second, first)) 
     case _ => { 
     val cycledList = cycles(nums) 
     cycledList.flatMap { cycle => 
      val h = cycle.head 
      val t = cycle.tail 
      val permutedList = permute(t) 
      permutedList map { pList => 
      h :: pList 
      } 
     } 
     } 
    } 
    } 
    val l = permute(List(1, 2, 3, 4)) 
    l foreach println 
    println(l.size) 
}