Swap list nodes

June 25, 2013

This is tricky. There are four possibilities:

1) If the list has less than k items (including the null list), return the list unchanged.

2) If the list has exactly 2k−1 items (the kth item is in the middle), return the list unchanged.

3) If the list has more than 2k−1 items, swap items k and nk, where k is before nk in the list.

4) If the list has less than 2k−1 items, swap items nk and k, where nk is before k in the list.

This can be done in a single pass using three pointers: Pointers a and b start from the beginning of the list and traverse k−1 nodes; if they reach the end of the list before traversing k−1 nodes, the original input list is returned unchanged. Then pointer b, which is still at the kth node, and pointer c, which is still at the beginning of the original input list, traverse nodes until b reaches the end of the list, at which point c points to the node k before the end of the list. If a and c point to the same node, return the original input list unchanged. Otherwise, swap the nodes pointed to by a and c and return the modified list. Here is our implementation:

(define (swap-kth-nodes xs k)
  (let loop1 ((a xs) (b xs) (k (- k 1)))
    (if (null? a) xs
      (if (positive? k) (loop1 (cdr a) (cdr b) (- k 1))
        (let loop2 ((b b) (c xs))
          (if (pair? (cdr b)) (loop2 (cdr b) (cdr c))
            (if (eq? a c) xs
              (let ((t (car a)))
                (set-car! a (car c)) (set-car! c t)
                  xs))))))))

The eq? performs pointer comparison; if a and c point to the same thing. Scheme provides that comparison because sometimes comparing pointers is quicker than comparing the objects to which the pointers point. Here are our tests:

> (swap-kth-nodes '() 3)
()
> (swap-kth-nodes '(1) 3)
(1)
> (swap-kth-nodes '(1 2) 3)
(1 2)
> (swap-kth-nodes '(1 2 3) 3)
(3 2 1)
> (swap-kth-nodes '(1 2 3 4) 3)
(1 3 2 4)
> (swap-kth-nodes '(1 2 3 4 5) 3)
(1 2 3 4 5)
> (swap-kth-nodes '(1 2 3 4 5 6) 3)
(1 2 4 3 5 6)
> (swap-kth-nodes '(1 2 3 4 5 6 7) 3)
(1 2 5 4 3 6 7)
> (swap-kth-nodes '(1 2 3 4 5 6 7 8) 3)
(1 2 6 4 5 3 7 8)
> (swap-kth-nodes '(1 2 3 4 5 6 7 8 9) 3)
(1 2 7 4 5 6 3 8 9)

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

About these ads

Pages: 1 2

4 Responses to “Swap list nodes”

  1. ;; 1- test cases:

    (defun test/swap-kth ()
    (loop
    :for (expected list k) :in ‘((() () 0)
    (() () 1)
    ((x) (x) 0)
    ((x) (x) 1)
    ((b a) (a b) 0)
    ((b a) (a b) 1)
    ((a b) (a b) 2)

    ((c b a) (a b c) 0)
    ((a b c) (a b c) 1)
    ((c b a) (a b c) 2)
    ((a b c) (a b c) 3)

    ((d b c a) (a b c d) 0)
    ((a c b d) (a b c d) 1)
    ((a c b d) (a b c d) 2)
    ((d b c a) (a b c d) 3)
    ((a b c d) (a b c d) 4)

    )
    :for mutable = (copy-list list)
    :for result = (swap-kth mutable k)
    :do (assert (equal expected mutable)
    () "(~S ‘~S ~S) -> ~S instead of expected ~S"
    ‘swap-kth list k result expected))
    :success)

    ;; 2- a correct implementation.

    (defun swap-kth (list k)
    (check-type k (integer 0))
    (when (< k (length list))
    (rotatef (nth k list) (nth (- (length list) k 1) list)))
    list)

    (test/swap-kth)
    ;; –> :success

    ;; Notice that this correct implementation is O(n) time and O(1)
    ;; space, so it’s not bad. But it walks the list up to 4 times (could
    ;; be 3 times, factorizing out (length list).

    ;; We can write an optimized solution that walks the list only up to 2
    ;; times with O(1) space, or only once with O(n) space.

    ;; 3- an optimized solution, with still O(1) space:
    ;; we walk the list once to compute the length, and then down
    ;; (max k (- length k 1)).

    (defun swap-kth (list k)
    (check-type k (integer 0))
    (let ((len (length list))) ; 1st walk.
    (when (< k len)
    (let* ((l (- len k 1))
    (i (min k l))
    (j (max k l))
    (a (nthcdr i list))
    (b (nthcdr (- j i) a)))
    (rotatef (car a) (car b))))
    list))

    (test/swap-kth)
    ;; –> :success

    ;; 4- an optimized solution using Θ(n) space, but amortized only Θ(n)
    ;; time, walking the list only once. It builds a vector parallel
    ;; to the list.

    (defun swap-kth (list k)
    (check-type k (integer 0))
    (let ((v (make-array 1 :adjustable t :fill-pointer 0)))
    (loop
    :for cell :on list
    :do (vector-push-extend cell v (array-dimension v 0)))
    (let ((len (length v))) ; O(1)
    (when (< k len)
    (let* ((l (- len k 1)))
    (rotatef (car (aref v k)) (car (aref v l))))))
    list))

    (test/swap-kth)
    ;; –> :success

  2. JP said

    Here’s a Rackety version (although this one should work in most any Scheme): Swap list nodes on jverkamp.com

    ; Given a list, swap the kth from head and tail
    (define (swap-kth ls k)
      ; Get pointers to the kth head and the kth tail
      (define-values (_ kth-head kth-tail)
        (let loop ([i 1] [ls ls])
          (cond
            [(null? ls)
             (values 1 #f #f)]
            [else
             (define-values (j kth-head kth-tail)
               (loop (+ i 1) (cdr ls)))
             (values
              (+ j 1)
              (if (= i k) ls kth-head)
              (if (= j k) ls kth-tail))])))
      
      ; Recur again, swapping the pointers
      (let loop ([ls ls])
        (cond
          [(null? ls)        '()]
          [(eq? ls kth-head) (cons (car kth-tail) (loop (cdr ls)))]
          [(eq? ls kth-tail) (cons (car kth-head) (loop (cdr ls)))]
          [else              (cons (car ls) (loop (cdr ls)))])))
    

    Check out the link above for test cases and a bit of discussion. Two9 things that were particularly neat was the use of eq? for quick pointer comparison and the relative simplicity of the code so far as dealing with special cases goes. Granted, it doesn’t bail early if kth-head is eq? to kth-tail, but that would be easy enough to add.

  3. fisherro said

    Here’s my version. Not particularly elegant.

    (define (swap a b)
      (define (swap_ k xs)
        (define len (length xs))
        (define (swap__ k xs)
          (let ((k1 (+ k 1)))
            (append
              (take k xs)
              (list (list-ref xs (- len k1)))
              (take (- len (* k1 2))
                    (drop k1 xs))
              (list (list-ref xs k))
              (drop (- len k)
                    xs))))
        (define k1 (+ k 1))
        (cond ((or (< k 0)
                   (< len 1)
                   (>= k len)
                   (= k1 (/ (+ len 1)
                            2)))
               xs)
              (else (swap__ (if (> k1 (/ len 2))
                              (- len k1)
                              k)
                            xs))))
      (cond ((and (integer? a)
                  (list? b))
             (swap_ a b))
            ((and (integer? b)
                  (list? a))
             (swap_ b a))
            (else #f)))
    

    The real work is done in swap__ appending the results of a take, a drop-take, a drop, and two list-refs. The swap_ function just checks for edge cases. The body of the outer function checks the types of the parameters and allows the user to pass them in either order.

  4. pytonist said


    def change_list(mylist,place):
    temp = mylist[place-1]
    mylist[place-1] = mylist[len(mylist)-place]
    mylist[len(mylist)-place] = temp
    return mylist

    mylist = [1,2,3,4,5,6,7,8,9]
    print (change_list(mylist,6))

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

%d bloggers like this: