Listing combinations WITH repetitions in Scala

combinatorics, scala

Solution

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

Problem

Original source