Hi All,
I am looking for a list based algorithm, that solves this problem:
Input: A list xs of numbers.
Output: Two lists of numbers ys and zs whose
lengths differ at most by one, and:
for all y in yz and z in zs: y<=z
A simple solution using sort is
(split-at (sort xs <) (half (length xs))
but using sort must be inefficient.
Another try (that doesn't work):
(let ([m (median xs)])
(partition (λ (x) (<= x m)) xs))
To see the bug here, try xs = (1 2 2 2 2 2 2).
Since the median in this case is 2, partion will return
two values, one is xs and one is the empty list.
--
Jens Axel Søgaard
____________________
Racket Users list:
http://lists.racket-lang.org/users
