Concatenação recursiva de listas

[Rafael Afonso]

Olá:

No programa abaixo tenho uma lista formada por 'a', 'b' e 'c', e quero
que seja retornada uma lista com as combinações possíveis com 0 a três
elementos:

//
-----------------------------------------------------------------------------
def juntar(letras: List[Char]): List[String] = {

def execute(chars: List[Char], string: String): List[String] =
chars match {
case Nil => List(string)
case letra :: outrasLetras => execute(outrasLetras, string +
letra) ::: execute(outrasLetras, string)
}

execute(letras, "")
}

println(juntar(List('a', 'b', 'c')))
//
-----------------------------------------------------------------------------

O resultado obtido foi List(abc, ab, ac, a, bc, b, c, ) - foi incluída
uma String vazia.
O problema é que essa abordagem tem duas desvantagens: A Tail
Recursion vai para o lixo; Além disso os resultados não estão em ordem
alfabética - ou seja, não estão na ordem da lista orginal.
Depois tentei uma outra abordagem que usa Tail Recursion:

//
-----------------------------------------------------------------------------
def juntar(letras: List[Char]): List[String] = {

def execute(chars: List[Char], strings: List[String]): List
[String] = chars match {
case Nil => strings
case letra :: outrasLetras =>
val outras = strings.map(_ + letra)
execute(outrasLetras, strings ::: outras)
}

execute(letras, List(""))
}

println(juntar(List('a', 'b', 'c')))
//
-----------------------------------------------------------------------------
O resultado obtido foi List(, a, b, ab, c, ac, bc, abc) - também foi
incluída uma String vazia. A ordem está uma pouco mais "alfabética".
Alguém tem uma idéia melhor de como realizar uma concatenação
recursiva de listas? (será que essa é realmente uma boa descrição do
problema?)

Grato,

Rafael U. C. Afonso