Skip to main content
1 of 2

Beginner: combinations with replacement

I am still new to scala and wrote a small snippet to find all the combinations with replacement of a sequence, e.g. cwr(ab, 3) should give aaa, aab, abb, bbb. The slow way would be to generate all permutations, sort them, and throw out duplicates. I'd like to know if this code is idiomatic scala style, and if I'm making any bad performance mistakes.

def sortedRanges(lo: Int, hi: Int, reps: Int) : List[List[Int]] =
    if (reps == 0) List(Nil) else (
    List.range(lo,hi).flatMap( 
        (x:Int) => (sortedRanges(x,hi,reps-1).map((xs:List[Int]) => x :: xs ))
    )
)

def combinations_with_replacement[T](stuff: List[T], reps: Int) : List[List[T]] = 
  sortedRanges(0,stuff.length, reps).map( (xs:List[Int]) => xs.map(stuff(_)))