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.
Simple enough in Python:
Even simpler in Haskell:
spl xs = splitAt (length xs `div` 2) xs
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:
whoops, no need for that return statement at the end of hsplit.
def split(aList):
cut = len(aList) / 2
firstH = aList[:cut]
secondH = aList[cut:]
return firstH,secondH
Oneliner solution in perl, basic tests included:
http://pastebin.com/GtduSYTg
or if you:
you can do
Oops, I meant to say it’s ruby… Another way with the second approach:
Another Perl solution. Works for empty and single-element lists as well.
Handles empty list and single element lists as well.
Clojure example:
(defn split [lst]
(let [half-count (int (/ (count lst) 2))]
[(take half-count lst) (drop half-count lst)]))
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.
For testing, a mapping from Python lists to pair chains and back.
Sourcecode tag, please work.
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.
One liner in Python.
ruby solution (http://codepad.org/C0JQX0rw)