Reversing Parts Of A List

December 3, 2013

For the first exercise, we take the car and cadr of a list, as long as they are not null, write them in reverse order to a result list, and stop at the end, when we reverse the entire list:

(define (rev-2 xs)
  (let loop ((xs xs) (zs (list)))
    (cond ((null? xs) (reverse zs))
          ((null? (cdr xs)) (reverse (cons (car xs) zs)))
          (else (loop (cddr xs) (cons (car xs) (cons (cadr xs) zs)))))))

> (rev-2 '(1 2 3 4 5 6))
(2 1 4 3 6 5)
> (rev-2 '(1 2 3 4 5))
(2 1 4 3 5)

For the second exercise, we make use of the auxiliary functions take and drop from the Standard Prelude to repeatedly collect k elements from the list, append them to a result list, and finally reverse the result; this works properly at the tail end of the list because both take and drop return less than k elements at the end of the list:

(define (rev-k k xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? xs) (reverse zs)
      (loop (drop k xs) (append (take k xs) zs)))))

> (rev-k 3 '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-k 4 '(1 2 3 4 5 6))
(4 3 2 1 6 5)

The third exercise uses Raymond Floyd’s tortoise-and-hare algorithm to race two pointers through the list, one twice as fast as the other; when the hare gets to the end of the list, the tortoise points to the middle of the list. The elements of the first half of the list are collected as the tortoise walks the list; the result is assembled when the hare reaches the end:

(define (rev-half xs)
  (let loop ((t xs) (h xs) (zs (list)))
    (cond ((null? h) (append zs (reverse t)))
          ((null? (cdr h)) (append zs (reverse t)))
          (else (loop (cdr t) (cddr h) (cons (car t) zs))))))

> (rev-half '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-half '(1 2 3 4 5))
(2 1 5 4 3)

You can run the program at http://programmingpraxis.codepad.org/WGr77ExY.

About these ads

Pages: 1 2

5 Responses to “Reversing Parts Of A List”

  1. Josef Svenningsson said

    Haskell solutions. They’re written in rather different style.

    module Reverse where
    
    reversePairs :: [a] -> [a]
    reversePairs (a:b:as) = b : a : reversePairs as
    reversePairs as       = as
    
    reverseK :: Int -> [a] -> [a]
    reverseK k as = go k [] as
      where go 0 rs as = rs ++ go k [] as
            go n rs (a:as) = go (n-1) (a:rs) as
            go _ rs [] = rs
    
    reverseHalves :: [a] -> [a]
    reverseHalves ls = let (as,bs) = splitAt (length ls `div` 2) ls
                       in reverse as ++ reverse bs
    
  2. Paul said

    In Python.

    from itertools import izip_longest
    
    # FILL for izip_longest - make sure that None can be used in the array
    FILL = object()
    
    def inv_k(arr, k):
        """invert k items"""
        it = iter(arr)
        res = []
        for p in izip_longest(*([it]*k), fillvalue=FILL):
            while p[-1] == FILL:
                p = p[:-1]
            res += reversed(p)
        return res
        
    def inv_pairs(arr):
        return inv_k(arr, 2)
        
    def inv_half(arr):
        return inv_k(arr, (len(arr) + 1) // 2)
    
  3. treeowl said

    Pairwise reversal:

    pairrev (x1:x2:xs) = x2:x1:pairrev xs
    pairrev stub = stub
    
    k-way reversal:
    import Data.List.Split
    krev k = concatMap reverse . splitEvery k
    
    revhalf l = case splitAt (l `quot` 2) l of
      (f, r) -> reverse f ++ reverse r
    
  4. Charlie said

    Would love to hear input on my method. Thanks.

    
    package praxis;
    
    import java.util.LinkedList;
    
    public class Praxis {
    
        public static void main(String[] args) {
            LinkedList<Integer> seq = new LinkedList<Integer>();
            seq.add(1);
            seq.add(2);
            seq.add(3);
            seq.add(4);
            seq.add(5);
            seq.add(6);
            seq.add(7);
            seq.add(8);
            seq.add(9);
            seq.add(10);
            seq.add(11);
            
            int k = 3;
            
            System.out.println(reversal(seq,2));
            System.out.println(reversal(seq,k));
            System.out.println(reversal(seq,seq.size()/2));
        }
        
        public static LinkedList<Integer> reversal(LinkedList<Integer> a,int k) {
            LinkedList<Integer> rev = new LinkedList<Integer>();
            for(int i=0;i<a.size();i=i+k){
                int idx_sec = (i+k-1);
                for(int j=0;j<k;j++){
                    if(idx_sec < a.size()) {
                        rev.add(i+j,a.get(idx_sec-j));
                    }
                    else{
                        if(rev.size() != a.size()){
                            rev.add(i+j,a.get(a.size()-j-1));
                        }
                    }
                }
            }
            return rev;
        }
    }
    

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 612 other followers

%d bloggers like this: