Programming Praxis

4 Responses to “Swap list nodes”

1. Pascal Bourguignon said

   June 25, 2013 at 6:26 PM

   ;; 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

   June 26, 2013 at 3:19 PM

   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

   July 17, 2013 at 6:56 PM

   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

   December 30, 2013 at 3:51 PM

   
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))