Sublists of lists using recursion in scala

Question

I tried to look for some algorithms to find all of the sub lists of a given list and this is what I found:

The only sublist of the empty list is the empty list. The sublists of x:xs (i.e. the list with the head x and the tail xs) are all of the sublists of xs as well as each of the sublists of xs with x prepended to them.

taken from Sublists of a list using list comprehension

Here is what I implemented:

    def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match{
    case List() => List()
    case x::xs => combinations(xs) ::: combinations(x :: xs)

  }

This function gives a stack overflow error as I expected however in the example from that question it worked for him. It might've been that I misunderstood the principle he explained? How could I tackle such a problem using recursion? Where was my mistake here?

Where can I look for such an algorithm?

@Daenyth Yes. That is correct. Check Kigyo answer. As I can see this algorithm now, it fails for my cases. Do you know a better algorithm? — Bula
– Bula, Commented Jun 10, 2014 at 20:12

Kigyo · Accepted Answer · 2014-06-10 19:57:36Z

3

This would be the algorithm according to your stated definition.

For the empty List, return a List with an empty List.

For the other case, use recursion to get all combinations from the tail and then additionally combine the head with each element from the result (tailComb). (tailComb.map(sub => x :: sub)).

def combinations[A](list: List[A]): List[List[A]] = list match {
  case Nil => List(List.empty[A])
  case x::xs => {
    val tailComb = combinations(xs)
    tailComb ::: tailComb.map(sub => x :: sub)
  }
}

answered Jun 10, 2014 at 19:57

Kigyo

5,7681 gold badge24 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Bula Over a year ago

Looks like the algorithm doesn't work in my cases if this is what it translates to. What better algorithm would you recommend me? ( I don't want code. I just want a name of an algorithm or a link if you could tell me)

Kigyo Over a year ago

Why does it not work? This is the definition you gave me. What can I recommend when you don't tell me what you want? Give an example.

Bula Over a year ago

Sublists of lists using recursion in scala as the title states. If you want more clarification: [1,2,3] = [1,2],[1],[2],[3],[2,3] and so on

Kigyo Over a year ago

combinations([1,2,3]) gives [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]. Is that not what you want?

Bula Over a year ago

Hm. My bad. My test was based on a List[(Char,Int)] for which it did compile but didn't show all the results. My question wasn't that however so I will mark this as accepted

|

Collectives™ on Stack Overflow

Sublists of lists using recursion in scala

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related