Mã để liệt kê các hoán vị trong Scala

Question

Tôi đã mã hóa một hàm để liệt kê tất cả hoán vị của một danh sách đã cho. Bạn nghĩ gì về mã dưới đây?

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

Cho một Seq, người ta có thể có hoán vị bằng cách gọi phương thức 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) 

Hơn nữa đó cũng là một phương pháp để combinations:

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

Về thực hiện của bạn tôi sẽ nói ba điều:

(1) của nó tốt trông

(2) Cung cấp một trình lặp (là phương pháp bộ sưu tập tiêu chuẩn cho phép loại bỏ các phần tử). Nếu không, bạn có thể nhận được danh sách với 1000! các yếu tố có thể không vừa trong bộ nhớ.

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) Bạn nên loại bỏ hoán vị trùng lặp (theo quan sát của Luigi), vì:

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

Tôi nghĩ rằng chức năng như vậy đã tồn tại trong thư viện chuẩn: Seq.permutations. Vậy tại sao lại phát minh lại bánh xe?

Answer 3

Hãy xem xét sự khác biệt ở đây: phiên bản của bạ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) 

Phiên bản tham khảo:

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

Answer 4

I đoán bạn đang thực hành kỹ năng lập trình Scala của bạn. Dưới đây là một số khác, trong đó ý tưởng là lấy các phần tử khác nhau làm đầu chuỗi và lặp lại được xóa qua filter. Độ phức tạp của mã sẽ là tốt, vì O (n) + O (n hoặc có thể n^2) + O (n) * P (n-1) bị chi phối bởi O (n) * P (n-1), trong đó P (n) là số hoán vị và không thể cải thiện được.

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

Có lẽ chủ đề này cũng đã được bão hòa, nhưng tôi nghĩ rằng tôi muốn vứt giải pháp của tôi vào sự pha trộn:

Giả sử không có các yếu tố lặp lại:

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 
} 

Với các yếu tố lặp lại, ngăn không cho các bản sao (không đẹp):

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 
} 

Đó có thể không phải là "danh sách-y" nhất rằng nó sử dụng slice và một chỉ mục trong danh sách, nhưng nó khá súc tích và có cách nhìn hơi khác. Nó hoạt động bằng cách chọn ra từng phần tử trong danh sách và tính toán các hoán vị của những gì còn lại, và sau đó ghép nối phần tử đơn với từng hoán vị đó. Nếu có một cách thành ngữ hơn để làm điều này, tôi rất muốn nghe về nó.

Answer 6

Tôi nghĩ rằng giải pháp của tôi là tốt hơn so với những người khác

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) 

Đây là cùng 3 dòng mã nhưng độ dài hoán vị biến được hỗ trợ và danh sách concatenations được loại bỏ.

Tôi đã thực hiện thành ngữ thứ hai hơn (do đó việc tích hợp bản đồ phẳng của bộ tích lũy được ngăn chặn, điều này cũng làm cho nó trở nên đệ quy hơn) và mở rộng thành hoán vị nhiều lần, để bạn có thể nói "aab", "aba "và" trừu kêu "là hoán vị (của nhau). Ý tưởng là chữ "a" có thể thay thế hai lần thay vì vô hạn (với trường hợp thay thế) hoặc chỉ có một lần (không có thay thế). Vì vậy, bạn cần một bộ đếm, trong đó cho bạn biết bao nhiêu lần mỗi lá thư là avaiable để thay thế.

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

Như generalizaiton, bạn có thể lấy/không thay thế bằng multisets funciton. Ví dụ,

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

Đây là một phiên bản dựa trên 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

Đây là một thực hiện mà là dựa trên khái niệm về chu kỳ và thực hiện tầm thường của hoán vị với hai yếu tố. Nó không xử lý các điểm trùng lặp và ngăn xếp tràn trong phương pháp tính toán

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