December 30, 2011

We use the tortoise-and-hare algorithm, where a tortoise walks the list, a hare runs the list at double speed, and the split occurs at the tortoise when the hare reaches the end of the list; note there is no need to count the number of elements in the list:

(define (split xs)
  (let loop ((ts xs) (hs xs) (zs (list)))
    (if (or (null? hs) (null? (cdr hs)))
        (values (reverse zs) ts)
        (loop (cdr ts) (cddr hs) (cons (car ts) zs)))))

Here ts is the remaining list of items unvisited by the tortoise, hs is the remaining list of items unvisited by the hare, and zs is the list of items already visited by the tortoise, in reverse order.

Here are some examples:

> (split '())
> (split '(1))
> (split '(1 2))
> (split '(1 2 3)
(2 3)
> (split '(1 2 3 4))
(1 2)
(3 4)
> (split '(1 2 3 4 5))
(1 2)
(3 4 5)

You may recall that we used the same tortoise-and-hare algorithm to look for cycles in Pollard’s rho factorization algorithm. You can run the program at http://programmingpraxis.codepad.org/jwHWMEXX.

Pages: 1 2

16 Responses to “Split”

  1. Bogdan Popa said

    Simple enough in Python:

    def split(L): 
        median = int(len(L) / 2) 
        return L[:median], L[median:]
  2. Tante Hedwig said

    Even simpler in Haskell:


  3. ardnew said

    this isn’t one of perl’s more elegant applications.


    use strict;
    use warnings;
    sub hsplit($$$)
      my $m = int($n / 2);
    # usage example
    my @list = (1,2,3,4,5);
    my @ll = ();
    my @lr = ();
    print "left  = @ll\n";
    print "right = @lr\n";
  4. ardnew said


  5. Ikenna said

    def split(aList):
    cut = len(aList) / 2
    firstH = aList[:cut]
    secondH = aList[cut:]
    return firstH,secondH

  6. takacsv said

    Oneliner solution in perl, basic tests included:


  7. hc5duke said
    def split(a)

    or if you:

    class Array
      def split

    you can do

  8. hc5duke said


    class Array
      def split
  9. chadadavis said


    sub splitlist { 
        my $mid = @_ / 2 -1 ;
  10. Axio said

    Handles empty list and single element lists as well.

    (define (split-at l n)
        (if (zero? n)
          (values (reverse h) t)
    (define (split l)
      (let ((size (length l)))
  11. Clojure example:

    (defn split [lst]

  12. (define (split xs)
     (let-values (((a b) 
    	(displayln a) (displayln b)))
    (split '(1 2 3 4 5))
  13. Jussi Piitulainen said


    from functools import reduce
    def each(xs, *, head = True):
    def even(xs, *, head = True):
    def split(cs):
        left, rest = None, None
            left, rest = (left, head), tail


    def test(xs):
        left, rest = split(unlist(xs))

    Sourcecode tag, please work.

  14. DGel said


    #include <vector>
    #include <utility>
    template <typename T>
    	size_t middle = list.size()/2;
  15. adeepak said

    One liner in Python.

    def split_list(items):
    a, b = split_list(items)
    print a, b

Leave a Reply


WordPress.com Logo


Twitter picture


Facebook photo


Google+ photo


Connecting to %s


Get every new post delivered to your Inbox.

Join 686 other followers

%d bloggers like this: