복붙노트

[SCALA] 스칼라에서 열거 순열에 코드

SCALA

스칼라에서 열거 순열에 코드

나는 주어진 목록의 모든 순열을 열거하는 기능을 코딩. 아래의 코드를 어떻게 생각하십니까?

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 &lt-; permutations(tail); p1 &lt-; interleave(head, p0)) yield p1
  }
}

해결법

  1. ==============================

    1.서열을 감안할 때, 하나는 이미 순열 메소드를 호출하여 순열을 가질 수 있습니다.

    서열을 감안할 때, 하나는 이미 순열 메소드를 호출하여 순열을 가질 수 있습니다.

    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)
    

    게다가 조합하는 방법도있다 :

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

    구현에 관해서는 나는 세 가지를 말할 것입니다 :

    (1) 그 좋은 찾고

    (2) (성병 컬렉션은 그 폐기 요소 받을수 접근법) 반복기를 제공한다. 그렇지 않으면, 당신은 1000 목록을 얻을 수 있습니다! 메모리에 적합하지 않을 요소.

    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) (루이지에 의해 관찰로) 당신은 중복 순열을 제거해야합니다 이후 :

    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))
    
  2. ==============================

    2.여기의 차이를 고려 버전을

    여기의 차이를 고려 버전을

    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)
    

    기준 버전 :

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

    3.Seq.permutations : 나는 그런 기능이 이미 표준 라이브러리에있는 생각합니다. 다시 바퀴를 개혁 왜?

    Seq.permutations : 나는 그런 기능이 이미 표준 라이브러리에있는 생각합니다. 다시 바퀴를 개혁 왜?

  4. ==============================

    4.어쩌면이 스레드는 이미 잘 포화,하지만 난 믹스에 내 솔루션을 던져 줄 알았는데 :

    어쩌면이 스레드는 이미 잘 포화,하지만 난 믹스에 내 솔루션을 던져 줄 알았는데 :

    반복되지 않는 요소를 가정하지 :

    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
    }
    

    반복 요소 방지 중복 (하지 꽤)로 :

    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
    }
    

    그것은 잠재적으로 슬라이스하고 목록에 인덱스를 사용하는 주어진 가장 "목록-Y ', 아니지만, 오히려 간결하고 그것을보고 약간 다른 방법입니다. 이 목록의 각 요소를 지목하고 나머지 한 다음 그 순열 각각에 하나의 요소을 연결 무슨의 순열을 계산하여 작동합니다. 이 작업을 수행 할 수있는 더 관용적 방법이 경우에, 나는 그것에 대해 듣고 싶어요.

  5. ==============================

    5.여기 스팬에 기초하여 버전이다.

    여기 스팬에 기초하여 버전이다.

    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
    }
    
  6. ==============================

    6.나는 당신이 당신의 스칼라 프로그래밍 기술을 연습하는 것 같아요. 여기서 아이디어는 필터를 통해 제거되는 순서 및 반복 헤드와 같은 다른 요소들을 취할 또 다른 하나는,이다. 코드 복잡성이 미세한다 보낸 O (N) + O (N 아니면 N ^ 2) + O (N) * P (N-1)은 O (N)에 의해 지배된다 * P (N-1), 이 P (n)의 순열 번호가 개선 될 수없는 경우.

    나는 당신이 당신의 스칼라 프로그래밍 기술을 연습하는 것 같아요. 여기서 아이디어는 필터를 통해 제거되는 순서 및 반복 헤드와 같은 다른 요소들을 취할 또 다른 하나는,이다. 코드 복잡성이 미세한다 보낸 O (N) + O (N 아니면 N ^ 2) + O (N) * P (N-1)은 O (N)에 의해 지배된다 * P (N-1), 이 P (n)의 순열 번호가 개선 될 수없는 경우.

    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
      }
    }
    
  7. ==============================

    7.나는 내 솔루션은 다른 사람보다 더 생각

    나는 내 솔루션은 다른 사람보다 더 생각

      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)
    

    이 코드 만 변수 순열 길이의 같은 3 개 라인이 지원되며 목록 회씩 연결이 제거됩니다.

    내가 만든 두 번째 더 ideomatic (누적의 평면지도 병합도 만드는 방지하는 그래서 더 꼬리 재귀) 당신이 "AAB", "ABA"와 "매를 말할 수 있도록하고, MULTISET 순열로 확장 "(서로의) 순열이다. 아이디어는 그 편지 "A"(대체 케이스) 대신 무한히 대체 가능 두 번 또는 (교체하지 않고) availble을 한 번만입니다. 그래서, 당신은 모든 문자가 교체 avaiable이다 얼마나 많은 시간을 알려주는 카운터가 필요합니다.

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

    일반화로서, 당신은 대체 사용하여 멀티 세트 기능이없는 /로 얻을 수 있습니다. 예를 들어,

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

    당신이 더 많은 순열에 대해 관심이 있다면, 당신은 볼 수 있습니다

  8. ==============================

    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)
    
  9. ==============================

    9.이 사이클의 개념 및 두 요소를 교환하다의 단순 구현을 기반으로 구현된다. 그것은 교환하다 방식으로 중복 및 스택 오버 플로우 측면을 처리하지 않습니다

    이 사이클의 개념 및 두 요소를 교환하다의 단순 구현을 기반으로 구현된다. 그것은 교환하다 방식으로 중복 및 스택 오버 플로우 측면을 처리하지 않습니다

    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)
    }
    
  10. from https://stackoverflow.com/questions/8124440/code-to-enumerate-permutations-in-scala by cc-by-sa and MIT license