Scala Repeat Lists in Scala

Question

Trying to learn a little Scala and ran into this problem. I found a solution for all combinations without repetitions here , and I understand the idea somewhat, but some of the syntax mixed me up. I also don't think the solution is suitable for the repetition case. I was wondering if anyone could suggest some code from which I could work. I have a lot of material on combinatorics, and I understand the problem and iterative solutions, I'm just looking for a way for scala -y to do this.

thanks

Answer 1

Now I understand your question. I think the easiest way to achieve what you want is to do the following:

def mycomb[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(el <- l; sl <- mycomb(n-1, l dropWhile { _ != el } )) yield el :: sl } def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.removeDuplicates) 

The comb method simply calls mycomb to remove duplicates from the input list. Removing duplicates means that it’s easier later to check if the two elements are “the same”. The only change I made to your mycomb method is that when the method is called recursively, I highlight the elements that appear before el in the list. This means that the output will be duplicates.

 > comb(3, List(1,2,3)) > List[List[Int]] = List( List(1, 1, 1), List(1, 1, 2), List(1, 1, 3), List(1, 2, 2), List(1, 2, 3), List(1, 3, 3), List(2, 2, 2), List(2, 2, 3), List(2, 3, 3), List(3, 3, 3)) > comb(6, List(1,2,1,2,1,2,1,2,1,2)) > List[List[Int]] = List( List(1, 1, 1, 1, 1, 1), List(1, 1, 1, 1, 1, 2), List(1, 1, 1, 1, 2, 2), List(1, 1, 1, 2, 2, 2), List(1, 1, 2, 2, 2, 2), List(1, 2, 2, 2, 2, 2), List(2, 2, 2, 2, 2, 2)) 

Answer 2

Meanwhile, combinations have become an integral part of scala collections:

 scala> val li = List (1, 1, 0, 0) li: List[Int] = List(1, 1, 0, 0) scala> li.combinations (2) .toList res210: List[List[Int]] = List(List(1, 1), List(1, 0), List(0, 0)) 

As we can see, it does not allow repeating, but resolving them simply with combinations: List each element of your collection (from 0 to li.size-1) and map the element in the list:

 scala> (0 to li.length-1).combinations (2).toList .map (v=>(li(v(0)), li(v(1)))) res214: List[(Int, Int)] = List((1,1), (1,0), (1,0), (1,0), (1,0), (0,0)) 

Answer 3

The question was rephrased in one of the answers - I hope that the question itself will also be edited. Someone answered the right question. I will leave this code below if someone finds this useful.

This decision is confusing as hell. A “combination” without repetition is called a permutation. It might look like this:

 def perm[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(el <- l; sl <- perm(n-1, l filter (_ != el))) yield el :: sl } 

If the input list does not contain unique elements, as suggested in another answer, this can be a little more complicated. Instead of a filter that removes all elements, we only need to delete the first one.

 def perm[T](n: Int, l: List[T]): List[List[T]] = { def perm1[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(el <- l; (hd, tl) = l span (_ != el); sl <- perm(n-1, hd ::: tl.tail)) yield el :: sl } perm1(n, l).removeDuplicates } 

Just a little explanation. In the for field, we take each element of the list and return the lists consisting of it, followed by a permutation of all elements of the list, with the exception of the selected element.

For example, if we take List (1,2,3), we will compile the lists formed by 1 and perm (List (2,3)), 2 and perm (List (1,3)) and 3 and perm (List (1 , 2)).

Since we execute arbitrary variables, we keep track of how long each submutation can take. If the subpermutation is 0, it is important to return a list containing an empty list. Please note that this is not an empty list! If we returned Nil in case 0, there would be no element for sl in the calling variable, and the integer "for" would give Nil. Thus, sl will be assigned to Nil, and we will make a list of el :: Nil, as a result we get List (el).

I was thinking about the original problem and I will post my solution here for reference. If you meant that there were no duplicate elements in the response as a result of duplicating the elements in the input, just add removeDuplicates, as shown below.

 def comb[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(i <- (0 to (l.size - n)).toList; l1 = l.drop(i); sl <- comb(n-1, l1.tail)) yield l1.head :: sl } 

This is a little ugly, I know. I need to use toList to convert the range (returned by "to") to a list, so that "for" itself returned a List. I could end up with "l1", but I think it makes it clearer what I'm doing. Since there is no filter here, changing it to remove duplicates is much easier:

 def comb[T](n: Int, l: List[T]): List[List[T]] = { def comb1[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(i <- (0 to (l.size - n)).toList; l1 = l.drop(i); sl <- comb(n-1, l1.tail)) yield l1.head :: sl } comb1(n, l).removeDuplicates } 

Answer 4

I wrote a similar solution to the problem on my blog: http://gabrielsw.blogspot.com/2009/05/my-take-on-99-problems-in-scala-23-to.html

At first I thought about creating all possible combinations and deleting duplicates (or using sets that take care of the duplicates themselves), but since the problem was listed and all possible combinations would be too big, ve came up with a recursive solution to the problem:

to get combinations of size n, take one element from the set and add it to all combinations of sets of size n-1 of the remaining elements, combine combinations of size n of the remaining elements. What does the code do

  //P26 def combinations[A](n:Int, xs:List[A]):List[List[A]]={ def lift[A](xs:List[A]):List[List[A]]=xs.foldLeft(List[List[A]]())((ys,y)=>(List(y)::ys)) (n,xs) match { case (1,ys)=> lift(ys) case (i,xs) if (i==xs.size) => xs::Nil case (i,ys)=> combinations(i-1,ys.tail).map(zs=>ys.head::zs):::combinations(i,ys.tail) } } 

How to read:

I had to create a helper function that will "raise" the list to the list of lists

Logic is in the statement of conformity:

If you need all combinations of size 1 from the elements of the list, just create a list of lists in which each subscriber contains an element of the original (which is the function "elevator")

If the combinations represent the total length of the list, simply return a list in which the only element is a list of elements (there is only one possible combination!)

Otherwise, take the head and tail of the list, calculate all combinations of n-1 tail size (recursive call) and add the head to each of the resulting lists (.map (ys.head :: zs)) combine the result with all combinations of size n of the tail of the list (another recursive call)

Does it make sense?

Answer 5

Daniel - I'm not sure that Alex meant duplicates, maybe the following gives a more suitable answer:

 def perm[T](n: Int, l: List[T]): List[List[T]] = n match { case 0 => List(List()) case _ => for(el <- l.removeDuplicates; sl <- perm(n-1, l.slice(0, l.findIndexOf {_ == el}) ++ l.slice(1 + l.findIndexOf {_ == el}, l.size))) yield el :: sl } 

Launch from

 perm(2, List(1,2,2,2,1)) 

this gives:

 List(List(2, 2), List(2, 1), List(1, 2), List(1, 1)) 

Unlike:

 List( List(1, 2), List(1, 2), List(1, 2), List(2, 1), List(2, 1), List(2, 1), List(2, 1), List(2, 1), List(2, 1), List(1, 2), List(1, 2), List(1, 2) ) 

The ease inside the nested permanent call removes one "el" from the list, I believe there is a better way to do this, but I can't think of this.

Answer 6

This solution was posted on Rosetta Code: http://rosettacode.org/wiki/Combinations_with_repetitions#Scala

 def comb[A](as: List[A], k: Int): List[List[A]] = (List.fill(k)(as)).flatten.combinations(k).toList 

Answer 7

In fact, it is not clear what you are asking. This may be one of several things. First, there would be simple combinations of different elements in the list. Scala offers this using the combinations() method from collections. If the elements are different, the behavior is exactly what you expect from the classic definition of "combinations." For n-element combinations of p elements, there will be p! / N! (Pn)! output combinations.

If there are duplicate elements in the list, Scala will generate combinations with the element appearing more than once in the combinations. But there are only different possible combinations, and the element may be replicated as many times as there is at the input. It generates only a set of possible combinations, therefore repeating elements, but not repeating combinations. I'm not sure there is an iterator at the heart of this for the actual Set .

Now what you really mean, if I understand correctly, are combinations from a given set of different p elements, where an element can appear repeatedly n times in a combination.

Well, let's go back a bit to generate combinations when elements are repeated at the input, and you want to see repeating combinations in the output, the way to do this is simply to generate it using “brute force” using n nested loops. Note that in reality there is nothing rude, it is just a natural number of combinations, really, which is O (p ^ n) for small n, and you can not do anything about it. You must be careful to choose these values ​​correctly, for example:

 val a = List(1,1,2,3,4) def comb = for (i <- 0 until a.size - 1; j <- i+1 until a.size) yield (a(i), a(j)) 

resulting in

 scala> comb res55: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (1,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)) 

This generates combinations of these duplicate values ​​in a, first creating intermediate combinations 0 until a.size as (i, j) ...

Now, to create "combinations with repetitions", you just need to change the indices as follows:

 val a = List('A','B','C') def comb = for (i <- 0 until a.size; j <- i until a.size) yield (a(i), a(j)) 

will create

 List((A,A), (A,B), (A,C), (B,B), (B,C), (C,C)) 

But I'm not sure what the best way to generalize this to larger combinations.

Now I close what I was looking for when I found this post: a function to create combinations from input containing duplicate elements, with intermediate indices generated by combinations() . It's nice that this method creates a list instead of a tuple, so this means that we can really solve the problem using the "map card", which I'm not sure what anyone else suggested here, but it is pretty elegant and will make your love of FP and Scala grow a little more after you see her!

 def comb[N](p:Seq[N], n:Int) = (0 until p.size).combinations(n) map { _ map p } 

leads to

 scala> val a = List('A','A','B','C') scala> comb(a, 2).toList res60: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 1), Vector(1, 2), Vector(1, 3), Vector(1, 2), Vector(1, 3), Vector(2, 3))