All repetition permutations using scala

Question

I am looking for a scala way to give all permutations without repetition. I know that there are some publications on this site, but they seem to have a slightly different problem.

I am looking for all permutations with repetitions. For example:

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

Must issue:

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

I apologize if my problem has already been resolved, but I could not find it.

Thanks in advance.

EDIT:

My own approach (not compiling):

 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 is a member of an array of a class that contains all the characters to be combined.

Answer 1

 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 2

With Scalaz:

 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 3

This should work:

 val input = List('A','C','G') (input ++ input ++ input) combinations(3) toList 

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) 

And if you need the resulting permutations:

 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) 

You can leave toList , but there so you can see the results.

Answer 5

Nobody seems to have suggested the easiest, or at least easiest to read --- solution.

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

(This is syntactic sugar for the following composition of cards:

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

to which the Scala compiler translates the above for statement.)

Answer 6

In ScalaZ 7

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

Answer 7

Just by making more general answers starting with @opyate and @monnef:

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

This will generate a repeat permutation with size 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)) 

and

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