All possible sublists scheme

Question

I want to find all possible consecutive partitions of a lists:

(a b c d) => (((a) (b c d)) ((a b) (c d)) ((a b c) (d)) ((a) (b c) (d)) ((a b c d)) ((a) (b) (c) (d)))

What would be the easiest way to go about this? ideally without using counters.

Edit:

Here is an example of what I have been trying, but it doesn't quite work (it is supposed to give the answers in reverse, but that'd be ok):

(define split-list-help
  (lambda (l h a)
    (begin
      (display a)
      (if
       (null? (cdr l))
       (list (cons (cons (car l) a) h))
       (let
       [(a-nosplit (cons (car l) a))
        (h-split (if (null? a)
             (cons (list (car l)) h)
             (cons (list (car l)) (cons a h))))]
     (append  (split-list-help (cdr l) h-split '())
          (split-list-help (cdr l) h a-nosplit)))))))

(split-list-help '(a b c) '() '())

The idea is that we traverse the list item by item, at each step we can either split it or not, then we branch into two new iterations, one with splitting and one without splitting. This produces a result close to what I want but not quite.

Answer 1

The goal is to find a natural way of describing the problem using recursion. In order to find the sublists of (a b c d) we can focus on the element a. There are four different consecutive sublists containing a:

(a)  (a b)  (a b c)  (a b c d)

In each case we need to find the sublists of the remaining elements. All in all the result must be the collection of list that result from

combining (a)       with (sublists '(b c d))
combining (a b)     with (sublists   '(c d))
combining (a b c)   with (sublists     '(d))
combining (a b c d) with (sublists     ' ())

That is we have:

(sublists '(a b c d)) = (append (combine '(a)       (sublists '(b c d)))
                                (combine '(a b)     (sublists   '(c d)))
                                (combine '(a b c)   (sublists    '(d)))
                                (combine '(a b c d) (sublists     '())))

We note that we have described the sublists of a list four elements using a recursive call of sublists of only three elements. The base case (sublists '()) must return the empty list '().

The only remaining question is what combine does. Let's examine the relation between the input and ouput in the case

(combine '(a) (sublists '(b c d)))

The sublists of '(b c d) are:

( ((b) (c) (d))
  ((b) (c d)  )
  ((b c) (d)  )
  ((b c d)    ) )

So (combine '(a) (sublists '(b c d))) must return

( ((a) (b) (c) (d))
  ((a) (b) (c d)  )
  ((a) (b c) (d)  )
  ((a) (b c d)    ) )

The operation that preprends an element (the list '(a)) in front of a list is cons, so we can use map and cons in concert:

(define (combine x xss)
  (map (lambda (xs) (cons x xs)) ; function that prepends x to a list xs
       xss))

Now we have all pieces of the puzzle. I'll leave the final definition of sublists to you.