Split

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))
()
(1)
> (split '(1 2))
(1)
(2)
> (split '(1 2 3)
(1)
(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.

About these ads

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:

    spl xs = splitAt (length xs `div` 2) xs

  3. ardnew said

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

    as far as I know, perl does not allow you to return multiple lists. instead, we return a list of list references. this has the requirement of allocating our half-lists from the calling routine, and passing references to those half-lists to our hsplit routine:

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

    whoops, no need for that return statement at the end of hsplit.

  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:

    http://pastebin.com/GtduSYTg

  7. hc5duke said
    def split(a)
      [ a[0..a.length/2], a[a.length/2..-1] ]
    end
    

    or if you:

    class Array
      def split
        [ self[0, length/2], self[length/2..-1] ]
      end
    end
    

    you can do

    > [1, 2, 3, 4, 5].split
     => [[1, 2], [3, 4, 5]] 
    
  8. hc5duke said

    Oops, I meant to say it’s ruby… Another way with the second approach:

    class Array
      def split
        [ first(length/2), slice(length/2..-1) ]
      end
    end
    
  9. chadadavis said

    Another Perl solution. Works for empty and single-element lists as well.

    sub splitlist { 
        my $mid = @_ / 2 -1 ;
        $mid = 0 if $mid < 0 && @_;
        return [@_[0 .. $mid]], [@_[$mid+1 .. @_-1]];
    }
    
  10. Axio said

    Handles empty list and single element lists as well.

    (define (split-at l n)
      (let loop ((n n) (h '()) (t l))
        (if (zero? n)
          (values (reverse h) t)
          (loop (1- n) (cons (car t) h) (cdr t)))))
    
    (define (split l)
      (let ((size (length l)))
        (split-at l (quotient size 2))))
    
  11. Clojure example:

    (defn split [lst]
    (let [half-count (int (/ (count lst) 2))]
    [(take half-count lst) (drop half-count lst)]))

  12. (define (split xs)
     (let-values (((a b) 
    	(split-at-right xs (round (/ (floor (length xs)) 2)))))
    	(displayln a) (displayln b)))
    
    (split '(1 2 3 4 5))
    
  13. Jussi Piitulainen said

    Python to split a pair chain with the slow and fast enumeration of the elements as in the reference problem and solution.
    Pairs are (tail, head), so they look backwards when printed, but they match Python’s reduce which accumulates from left.

    from functools import reduce
    
    def pair(tail, head): return (tail, head)
    
    def each(xs, *, head = True):
        while xs: yield xs[bool(head)] ; xs = xs[0]
    
    def even(xs, *, head = True):
        while xs: yield xs[bool(head)] ; xs = xs[0] and xs[0][0]
    
    def split(cs):
        left, rest = None, None
        for head, tail, fast in zip(each(cs), each(cs, head = False), even(cs)):
            left, rest = (left, head), tail
        return reduce(pair, each(left), None), rest
    

    For testing, a mapping from Python lists to pair chains and back.

    def unlist(xs): return reduce(pair, reversed(xs), None)
    def relist(xs): return list(each(xs))
    
    def test(xs):
        left, rest = split(unlist(xs))
        print(list(xs), '=', relist(left), '+', relist(rest))
    

    Sourcecode tag, please work.

  14. DGel said

    C++ solution. A bit verbose, but well it’s c++ :) No need for the tortoise and hare solution, as the length of the list is already known.

    
    #include <vector>
    #include <utility>
    
    template <typename T>
    std::pair<std::vector<T>, std::vector<T> > split_list(std::vector<T> &list)
    {
    	size_t middle = list.size()/2;
    	std::vector<T> first(list.begin(), list.begin() + middle);
    	std::vector<T> second(list.begin() + middle, list.end());
    	return std::pair<std::vector<T>, std::vector<T> >(first, second);
    }
    
    
  15. adeepak said

    One liner in Python.

    
    def split_list(items):
        return items[:len(items)/2], items[len(items)/2:]
    
    items = [1, 2, 3, 4, 5]
    a, b = split_list(items)
    print a, b
    
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 617 other followers

%d bloggers like this: