Код для перечисления перестановок в 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

При задании Seq уже можно иметь перестановки, вызывая метод 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)

Кроме того, существует также метод для combinations:

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

Что касается вашей реализации, я бы сказал три вещи:

(1) Его хороший внешний вид

(2) Предоставить итератор (который представляет собой подход std-коллекций, который позволяет отбрасывать элементы). В противном случае вы можете получить списки с 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

Рассмотрим разницу здесь: ваша версия

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

Я думаю, что такая функция уже существует в стандартной библиотеке: Seq.permutations. Так зачем снова изобретать колесо?

Ответ 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

Вот версия, основанная на 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
}

Ответ 6

Думаю, вы практиковали свой навык программирования Scala. Вот еще одна идея, в которой идея состоит в том, чтобы принимать различные элементы в качестве главы последовательности, а повторы удаляются через filter. Сложность кода должна быть точной, так как 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

Я думаю, что мое решение лучше других

  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 строки кода, но поддерживаются переменные длины перестановок и исключаются конкатенации списков.

Я сделал второй более идеоматичным (чтобы предотвратить слияние плоских карт аккумулятора, что также делает его более хвостовым рекурсивным) и расширены в мультимножество перестановок, так что вы можете сказать, что "aab", "aba", и "baa" - это перестановки (друг друга). Идея состоит в том, что буква "а" заменяется без изменений дважды (с заменой) или заменяется только один раз (без замены). Итак, вам нужен счетчик, который сообщает вам, сколько раз каждая буква доступна для замены.

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

Как generalizaiton, вы можете получить с/без замены, используя multisets funciton. Например,

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

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

Это реализация, основанная на концепции цикла и тривиальной реализации перестановки с двумя элементами. Он не обрабатывает дубликаты и аспект в методе перестановки

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