Все перестановки с повторением с использованием scala

Question

Я ищу scala способ дать все перестановки без повторений. Я знаю, что на этом сайте уже есть некоторые сообщения, но у них, похоже, немного другая проблема.

Я ищу все перестановки с повторениями. Например:

combine(List('A','C','G'))

Должен дать:

List(List('A'.'A','A'),List('A'.'A','C'),List('A'.'A','G'),List('A'.'C','A'),
List('A'.'C',''C), ... List('G'.'G','G')

Извините, если моя проблема уже решена, но я не смог ее найти.

Заранее спасибо.

EDIT:

Мой собственный подход (не компилируется):

def combine(size: Int = sym.length) : List[List[T]] = {
  size match {
    case 0 => List()
    case 1 => sym.toList.map(List(_))
    case _ => for (el <- sym) yield el :: combine(size-1)
  }
}

sym - член массива класса, который содержит все символы для объединения.

Answer 1

С помощью Скалаза:

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> def combine[A](xs: List[A]): List[List[A]] = {
     |   xs.replicate[List](xs.size).sequence
     | }
combine: [A](xs: List[A])List[List[A]]

scala> combine(List('A', 'C', 'G'))
res47: List[List[Char]] = List(List(A, A, A), List(A, A, C), List(A, A, G), List
(A, C, A), List(A, C, C), List(A, C, G), List(A, G, A), List(A, G, C), List(A, G
, G), List(C, A, A), List(C, A, C), List(C, A, G), List(C, C, A), List(C, C, C),
 List(C, C, G), List(C, G, A), List(C, G, C), List(C, G, G), List(G, A, A), List
(G, A, C), List(G, A, G), List(G, C, A), List(G, C, C), List(G, C, G), List(G, G
, A), List(G, G, C), List(G, G, G))

Answer 2

Это должно работать:

val input = List('A','C','G')

(input ++ input ++ input) combinations(3) toList

Answer 3

def combinations(size: Int = sym.length) : List[List[T]] = {
    if (size == 0)
        List(List())
    else {
        for {
            x  <- sym.toList
            xs <- combinations(size-1)
        } yield x :: xs
    }
}

Answer 4

scala> def comb(s:String)=(s * s.length).combinations(s.length)
comb: (s: String)Iterator[String]

scala> comb("ACG").toList
res16: List[String] = List(AAA, AAC, AAG, ACC, ACG, AGG, CCC, CCG, CGG, GGG)

А если вы хотите получить перестановки:

scala> comb("ACG").flatMap(_.toSeq.permutations.toList).toList
res11: List[Seq[Char]] = List(AAA, AAC, ACA, CAA, AAG, AGA, GAA, ACC, CAC, CCA, ACG, AGC, CAG, CGA, GAC, GCA, AGG, GAG, GGA, CCC, CCG, CGC, GCC, CGG, GCG, GGC, GGG)

Вы можете пропустить toList, но он есть, чтобы вы могли видеть результаты.

Answer 5

Кажется, никто не предложил самое простое - или, по крайней мере, самое простое для чтения - решение. Это

myList = List("A", "C", "G")
for {
  i <- myList
  j <- myList
  k <- myList
} yield List(i,j,k)

(Это синтаксический сахар для следующего состава карт:

myList.flatMap(i => myList.flatMap(j => myList.map(k => List(i,j,k))))

, в который компилятор Scala переводит вышеприведенное выражение for.)

Answer 6

Просто сделать более общие ответы от @opyate и @monnef:

// considering that we want a permutation_size
List.fill(permutation_size)(input).flatten.combinations(permutation_size).toList

Это сгенерирует перестановку с повторением с размером permutation_size:

val a = List.fill(2)(List("A","B","C")).flatten.combinations(2).toList
a: List[List[String]] = List(List(A, A), List(A, B), List(A, C), List(B, B), List(B, C), List(C, C))

и

val a = List.fill(3)(List("A","B","C")).flatten.combinations(3).toList
a: List[List[String]] = List(List(A, A, A), List(A, A, B), List(A, A, C), List(A, B, B), List(A, B, C), List(A, C, C), List(B, B, B), List(B, B, C), List(B, C, C), List(C, C, C))

Answer 7

В ScalaZ 7

import scalaz._
import Scalaz._
def combinine[T](l: List[T]) = l.replicateM(l.size)