Lisp - Split list in n lists

Question

I can't think of way how to split list equally, for example this list:

(("6" "S") ("7" "S") ("8" "S") ("9" "S") ("10" "S") ("J" "S") ("K" "S")
 ("A" "S") ("6" "C") ("7" "C") ("8" "C") ("9" "C") ("10" "C") ("J" "C")
 ("Q" "C") ("K" "C") ("A" "C") ("6" "H") ("7" "H") ("8" "H") ("9" "H")
 ("10" "H") ("J" "H") ("Q" "H") ("K" "H") ("A" "H")("6" "D") ("7" "D")
 ("8" "D") ("9" "D") ("10" "D") ("J" "D") ("Q" "D") ("K" "D"))

into n lists, for example in 3 or 4 depending how much it is needed to split in. If in 3 lists then then list that should be returned should look like this:

(("6" "S") ("7" "S") ("8" "S") ("9" "S") ("10" "S") ("J" "S") ("K" "S")
 ("A" "S") ("6" "C") ("7" "C") ("8" "C") ("9" "C"))
(("10" "C") ("J" "C") ("Q" "C") ("K" "C") ("A" "C")("6" "H") ("7" "H")
 ("8" "H") ("9" "H") ("10" "H") ("J" "H") ("Q" "H"))
(("K" "H") ("A" "H")("6" "D") ("7" "D") ("8" "D") ("9" "D") ("10" "D")
 ("J" "D") ("Q" "D") ("K" "D"))

The first list will contain 12 elements, second 12 and the third one 11.

Answer 1

The following function splits a list into sublists of length len. If you want to use the number of sublists s instead of the length of each one of them, call it with (/ (length list) s):

(defun split-list (list len)
 ;; (split-list '(a b c d e f g) 3) => ((A B C) (D E F) (G))
 "Splits the list into sublists of length len. The last element might have fewer than len elements."
    (do* ((n 1 (1+ n))
          (l list (cdr l))
          (l1 nil)
          (res nil) )
         ((null l) (progn (when l1 (push (nreverse l1) res))(nreverse   res)))
        (push (car l) l1)
        (when (= n len)
            (push (nreverse l1) res)
            (setq l1 nil)
            (setq n 0) )))

Answer 2

i would probably do it this way (though it is more verbose than some of the solutions, i find it more readable and reusable)

first some utility functions:

(defun split-at (n data)
  (labels ((split-rec (n acc rest)
             (if (or (null rest) (zerop n)) 
                 (cons (nreverse acc) rest)
                 (split-rec (1- n) (cons (car rest) acc) (cdr rest)))))
    (split-rec n () data)))


;; this one would count the needed chunk sizes to cover different input cases
(defun chunk-lengths (data-len parts)
  (let ((chunk-size (floor (/ data-len parts)))
        (longer-chunks (rem data-len parts)))
    (nconc (loop :repeat longer-chunks :collect (1+ chunk-size))
           (loop :repeat (- parts longer-chunks) :collect chunk-size))))

and the partitioning function:

(defun split-into (chunks-count data)
  (nreverse 
   (car
    (reduce (lambda (acc len)
              (destructuring-bind (res . remaining-items) acc
                (destructuring-bind (l . r) (split-at len remaining-items)
                  (cons (push l res) r))))
            (chunk-lengths (length data) chunks-count)
            :initial-value (cons nil data)))))

CL-USER> (split-into 6 '(1 2 3 4 5 6 7 8 9))
;;=> ((1 2) (3 4) (5 6) (7) (8) (9))

CL-USER> (split-into 10  '(1 2 3 4 5))
;;=> ((1) (2) (3) (4) (5) NIL NIL NIL NIL NIL)

notice that this solution guarantees that you get just as many chunks as you requested (even if the collection is shorter than chunks count)

Answer 3

Here is a simple CL implementation using loop: this should be easy to understand I think. This kind of collect-a-bunch-of-things is what loop is particularly good at.

(defun partition-list (list parts &key (last-part-longer nil))
  ;; Partition LIST into PARTS parts.  They will all be the same
  ;; length except the last one which will be shorter or, if
  ;; LAST-PART-LONGER is true, longer.  Doesn't deal with the case
  ;; where there are less than PARTS elements in LIST at all (it does
  ;; something, but it may not be sensible).
  (loop with size = (if last-part-longer
                        (floor (length list) parts)
                      (ceiling (length list) parts))
        and tail = list
        for part upfrom 1
        while tail
        collect (loop for pt on tail
                      for i upfrom 0
                      while (or (and last-part-longer (= part parts))
                                (< i size))
                      collect (first pt)
                      finally (setf tail pt))))

Answer 4

if you look into scheme's take and drop functions you can achieve what you want. for example observe this simple procedure:

(define (splitparts lst num)
  (letrec ((recurse
            (lambda (lst num acc)
              (if (null? lst)
                acc
                (recurse (drop lst num) num (append acc (list (take lst num))))))))
    (recurse lst num '())))

> (splitparts '(1 2 3 4) 2)
((1 2) (3 4))
> (splitparts '(1 2 3 4 5 6 7 8) 2)
((1 2) (3 4) (5 6) (7 8))

now the problem with this is that you if take and drop expect the list to have at least the number of elements that you are requesting. so we can write our own versions that take up to some number of elements and if they get less they don't care. here is such an implementation of take as inspired by this thread with a properly tail recursive implementation

(define (takeup to lst)
  (letrec ((recurse
           (lambda (to lst acc)
             (if (or (zero? to) (null? lst))
               acc
               (recurse (- to 1) (cdr lst) (append acc (list (car lst))))))))
    (recurse to lst '())))

> (takeup 5 '(1 2 3))
(1 2 3)
> (takeup 5 '(1 2 3 4 5 6 7))
(1 2 3 4 5)

now you can easily write your splitparts function when you implement a similar dropupto function. In common lisp you have the subseq function that you can use to achieve functionality similar to take and drop.

EDIT: common lisp implementations of simple take and drop (please excuse my very non idiomatic CL)

;; recursive implemention of take just for demo purposes.
(defun takeinner (lst num acc)
  (if (or (= num 0) (null lst))
    acc
    (takeinner (cdr lst) (- num 1) (append acc (list (car lst))))))

(defun take (lst num)
  (takeinner lst num '()))

;; of course take can be implemented using subseq as drop.
(define take-alternative (lst num)
  (subseq lst 0 num))

(defun drop (lst num)
  (subseq lst num))

(defun splitpartsinner (lst num acc)
   (if (null lst)
        acc
       (splitpartsinner (drop lst num) num (append acc (list (take lst num))))))

(defun splitparts (lst num)
  (splitpartsinner lst num '()))

> (splitparts '(1 2 3 4) 2)
((1 2) (3 4))

this will suffer from the problem described above so you still have to implement the -up-to versions.

Answer 5

Try this

 (multiple-value-bind (sub-list-size inc)
       // returns the sublist size and the adjustment you may use on the last list
       // size is the number of lists you wish to create
       (round (length list) size)
     (let ((iteration 1)
           (final-list '())
           (sub-list '()))
         (dotimes (x (length list))
            (cond ((< iteration size)
              // if its not the last list, add to the sublist until you reach the limit
                    (cond ((< (length sub-list) sub-list-size)
                           (push (nth x list) sub-list))
                          (t 
                            // when you reach the limit, increment the iteration number and start a new sub list with the current number
                            (push (reverse sub-list) final-list)
                            (incf iteration)
                            (setf sub-list (list (nth x list))))))                        
                  (t
                    // in the last iteration, add to the sub list until you have no more elements
                    (push (nth x list) sub-list))))
          (push (reverse sub-list) final-list)
          (reverse final-list)))