List Slices

October 27, 2020

During some recent personal programming, I needed a function to slice a list into pieces: Given a list of sub-list lengths, and an input list to be sliced, return a list of sub-lists of the requested lengths. For instance:, slicing the list (1 2 2 3 3 3) into sub-lists of lengths (1 2 3) returns the list of sub-lists ((1) (2 2) (3 3 3)). Extra list elements at the end of the input list are ignored, missing list elements at the end of the input list are returned as null lists.

Your task is to write a program that slices lists into sub-lists according to a specification of sub-list lengths. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

5 Responses to “List Slices”

  1. chaw said

    Here is an implementation in standard Scheme with no additional dependencies.

    (import (scheme base)
            (scheme write)
            (only (srfi 8) receive))
    
    (define samples ; ((input . output) ...)
      '((((1 2 2 3 3 3) (1 2 3)) . ((1) (2 2) (3 3 3)))
        (((1 2 2 3 3 3) (2 3)) . ((1 2) (2 3 3)))
        (((1 2 2 3 3 3) (2 3 4)) . ((1 2) (2 3 3) (3)))
        (((1 2 2 3 3 3) (2 3 4 2)) . ((1 2) (2 3 3) (3) ()))
        (((1 2 2 3 3 3) (6 6 7)) . ((1 2 2 3 3 3) () ()))
        ((() (6 6 7)) . (() () ()))
        ((() ()) . ())))
    
    ;; Like SRFI-1 split-at, but without error if fewer than k items available
    (define (take-at-most+rest lst k)
      (let loop ((lst lst)
                 (k k)
                 (res '()))
        (if (or (null? lst)
                (not (positive? k)))
            (values (reverse res) lst)
            (loop (cdr lst)
                  (- k 1)
                  (cons (car lst)
                        res)))))
    
    (define (slice/lengths items slice-lengths)
      (let f ((xs items)
              (ls slice-lengths)
              (r '()))
        (if (null? ls)
            (reverse r)
            (receive (taken rest) (take-at-most+rest xs (car ls))
              (f rest
                 (cdr ls)
                 (cons taken r))))))
    
    (define (partial-apply-left proc . args)
      (lambda x (apply proc (append args x))))
    
    (define (demo f)
      (write (equal? (map cdr samples)
                     (map (partial-apply-left apply f) (map car samples))))
      (newline))
    
    (demo slice/lengths)
    

    Output:

    #t
    

  2. Zack said

    Here is my take on this using Julia 1.5: https://pastebin.com/MiMuvK3V

    Pretty straight-forward, through the types need some attention since there is no null for Integers, so I had to use Reals in the output array. Cheers!

  3. Daniel said

    Here are two solutions in Python, the first with explicit calculation of slicing indices, and the second relying on itertools.accumulate.

    def slice1(lst, lengths):
        output = []
        lengths = lengths[::-1]
        start = 0
        while lengths:
            end = start + lengths.pop()
            output.append(lst[start:end])
            start = end
        return output
    
    def slice2(lst, lengths):
        from itertools import accumulate
        acc = [0] + list(accumulate(lengths))
        return [lst[start:end] for start, end in zip(acc, acc[1:])]
    
    print(slice1([1, 2, 2, 3, 3, 3], [1, 2, 3]))
    print(slice1([1, 2, 2, 3], [1, 2, 3]))
    print(slice1([1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3]))
    
    print(slice2([1, 2, 2, 3, 3, 3], [1, 2, 3]))
    print(slice2([1, 2, 2, 3], [1, 2, 3]))
    print(slice2([1, 2, 2, 3, 3, 3, 4, 4, 4, 4], [1, 2, 3]))
    

    Output:

    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3]]
    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3, 3, 3]]
    [[1], [2, 2], [3]]
    [[1], [2, 2], [3, 3, 3]]
    
  4. matthew said

    Here’s a couple of Haskell solutions, one using an explicit recursion, the other doing a combined map and fold with mapAccumL:

    splitlist [] _ = []
    splitlist (n:s) t = take n t : splitlist s (drop n t) 
    
    import qualified Data.List
    import qualified Data.Tuple
    
    splitlist counts s = snd (Data.List.mapAccumL f s counts) where
      f s n = Data.Tuple.swap (splitAt n s)
    
  5. Mitchell said

    In common lisp by mapping a recursive function that returns a list of k elements from a list over the list of lengths.

    (defun slice-list (seq n)
    (labels ((rec (s k)
    (if (= k 0)
    nil
    (cons (car s)
    (rec (cdr s) (- k 1))))))
    (let ((offset 0))
    (map 'list
    (lambda (k)
    (let ((new-offset offset))
    (incf offset k)
    (rec (subseq seq new-offset) k)))
    n))))

    (slice-list '(1 2 2 3 3 3) '(1 2 3))
    ; ((1) (2 2) (3 3 3))

    (slice-list '(1 2 2 3 3 3) '(1 2 5))
    ;((1) (2 2) (3 3 3 NIL NIL))

    (slice-list '(1 2 2 3 3 3) '(1 2 1))
    ;((1) (2 2) (3))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: