Codice per enumerare le permutazioni in Scala

Question

Ho codificato una funzione per enumerare tutte le permutazioni di una determinata lista. Cosa ne pensi del codice qui sotto?

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

Dato un Seq, si può già avere permutazioni invocando il metodo 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) 

Inoltre v'è anche un metodo per combinations:

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

Per quanto riguarda l'implementazione direi tre cose:

(1) Il suo bell'aspetto

(2) Fornire un iteratore (che è l'approccio di collezioni std che permette di scartare gli elementi). Altrimenti, puoi ottenere liste con 1000! elementi che potrebbero non adattarsi alla 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) È necessario rimuovere permutazioni duplicati (come osservato da Luigi), dal momento che:

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

Penso che una tale funzione esiste già nella libreria standard: Seq.permutations. Allora perché reinventare la ruota di nuovo?

Answer 3

considerare la differenza qui: la versione

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 versione di riferimento:

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

Answer 4

I Indovina che stai esercitando le tue abilità di programmazione Scala. Eccone un altro, in cui l'idea è di prendere diversi elementi come capo di sequenza e le ripetizioni vengono rimosse attraverso filter. La complessità del codice andrà bene, poiché O (n) + O (n o forse n^2) + O (n) * P (n-1) è dominato da O (n) * P (n-1), dove P (n) è il numero di permutazione e non può essere migliorato,.

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

Forse questa discussione è già ben saturi, ma ho pensato di gettare la mia soluzione nel mix:

fatti salvi elementi di ripetizione:

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 gli elementi di ripetizione, impedendo duplicati (non come belle):

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 
} 

non è potenzialmente il più "lista-y", data che usa slice e un indice sulla lista, ma è piuttosto conciso e un modo leggermente diverso di guardarlo. Funziona individuando ciascun elemento nella lista e calcolando le permutazioni di ciò che è rimasto, e quindi concatenando il singolo elemento a ciascuna di quelle permutazioni. Se c'è un modo più idiomatico per farlo, mi piacerebbe saperlo.

Answer 6

ritengo che la soluzione mio è meglio di altri

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) 

Questi sono gli stessi 3 linee di codice concatenazioni ma sono supportate lunghezze variabili e permutazione elenco vengono eliminati.

Ho reso il secondo più ideologico (in modo da impedire l'unione di accumulatori di mappe piane, che rende anche più ricurvo in coda) e esteso in permutazioni multiset, in modo che si possa dire che "aab", "aba "e" baa "sono permutazioni (l'una dell'altra). L'idea è che la lettera "a" sia sostituibile due volte anziché infinitamente (con sostituzione) o disponibile solo una volta (senza sostituzioni). Quindi, hai bisogno di un contatore, che ti dice quante volte ogni lettera è disponibile per la sostituzione.

// 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) 

Come generalizzazione, è possibile ottenere con/senza sostituzioni utilizzando la funzione multiset. Per esempio,

//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

Ecco una versione basata su 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

Questa è un'implementazione che si basa sul concetto di ciclo e un'implementazione banale di permute con due elementi. Non gestisce i duplicati e aspetto stack overflow nel metodo 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) 
}