Listing combinations WITH repetitions in Scala

Question

Trying to learn a bit of Scala and ran into this problem. I found a solution for all combinations without repetions here and I somewhat understand the idea behind it but some of the syntax is messing me up. I also don't think the solution is appropriate for a case WITH repetitions. I was wondering if anyone could suggest a bit of code that I could work from. I have plenty of material on combinatorics and understand the problem and iterative solutions to it, I am just looking for the scala-y way of doing it.

Thanks

Answer 1

The question was rephrased in one of the answers -- I hope the question itself gets edited too. Someone else answered the proper question. I'll leave that code below in case someone finds it useful.

That solution is confusing as hell, indeed. A "combination" with repetitions is called permutation. It could go 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 is not guaranteed to contain unique elements, as suggested in another answer, it can be a bit more difficult. Instead of filter, which removes all elements, we need to remove just 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 bit of explanation. In the for, we take each element of the list, and return lists composed of it followed by the permutation of all elements of the list except for the selected element.

For instance, if we take List(1,2,3), we'll compose lists formed by 1 and perm(List(2,3)), 2 and perm(List(1,3)) and 3 and perm(List(1,2)).

Since we are doing arbitrary-sized permutations, we keep track of how long each subpermutation can be. If a subpermutation is size 0, it is important we return a list containing an empty list. Notice that this is not an empty list! If we returned Nil in case 0, there would be no element for sl in the calling perm, and the whole "for" would yield Nil. This way, sl will be assigned Nil, and we'll compose a list el :: Nil, yielding List(el).

I was thinking about the original problem, though, and I'll post my solution here for reference. If you meant not having duplicated elements in the answer as a result of duplicated elements in the input, just add a 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
}

It's a bit ugly, I know. I have to use toList to convert the range (returned by "to") into a List, so that "for" itself would return a List. I could do away with "l1", but I think this makes more clear what I'm doing. Since there is no filter here, modifying 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 2

Daniel -- I'm not sure what Alex meant by duplicates, it may be that the following provides a more appropriate 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
}

Run as

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

this gives:

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

as opposed to:

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 nastiness inside the nested perm call is removing a single 'el' from the list, I imagine there's a nicer way to do that but I can't think of one.

Answer 3

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

First I thought of generating all the possible combinations and removing the duplicates, (or use sets, that takes care of the duplications itself) but as the problem was specified with lists and all the possible combinations would be too much, I've came up with a recursive solution to the problem:

to get the combinations of size n, take one element of the set and append it to all the combinations of sets of size n-1 of the remaining elements, union the combinations of size n of the remaining elements. That's what the code does

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

I had to create an auxiliary function that "lift" a list into a list of lists

The logic is in the match statement:

If you want all the combinations of size 1 of the elements of the list, just create a list of lists in which each sublist contains an element of the original one (that's the "lift" function)

If the combinations are the total length of the list, just return a list in which the only element is the element list (there's only one possible combination!)

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

Does it make sense?

Answer 4

Okay, I guess my explanation was not very good, but I appreciate all the responses and they are helping me understand more of the syntax of scala. Basically I need to choose r items from n types with repetition of items allowed, but order is unimportant.

So for the list (1,2,3) the formula is C(n=3, r=3) = (n+r-1)! / r!(n-1)! = 10 possible combinations that I would like to list. The list would then look like:

{1,1,1} {1,1,2} {1,1,3} {1,2,2} {1,2,3} {1,3,3} {2,2,2} {2,2,3} {2,3,3} {3,3,3}

So I can choose "1" three times, but since order does not matter we can discard sets such {2,1,1}.

I have come up with this simple function:

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))
        yield el :: sl
}

which gives the repetitions as I would like, but does not remove items that are just in a different order. I think the solution is once the entire outside loop runs for an element, to then remove that element from the list. However, I cannot quite 'see' how this would be done in the given syntax. I would also think a filter or remove operation on the result could work, but I wasn't sure how would compare all the elements of a list against each other. I know that using the diff (--) operator we can see if 2 lists are just re-ordered but the same.

Answer 5

Hi Alex,

I understand your question now. 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 just calls mycomb with duplicates removed from the input list. Removing the duplicates means it is then easier to test later whether two elements are 'the same'. The only change I have made to your mycomb method is that when the method is being called recursively I strip off the elements which appear before el in the list. This is to stop there being duplicates in the output.

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