List Swap

December 13, 2016

This would be easier if we knew the length of the list before we started, but the problem is silent as to the length of the list, so assume that we don’t know the length of the list a priori, and of course we don’t know if the indices cross. We must be sure to report an error if the length of the list is less than k, and properly handle the case where k is the central item of an odd-length list.

Our algorithm runs through the list, shifting items from front to back and saving the kth item, then makes a second pass back to front, rewriting the list as it goes; variable qs restarts the indexing at the start of the list, so it points to the n-kth item when iteration stops:

(define (swap k xs)
  (if (< k 1) (error 'swap "don't be silly")
    (let loop1 ((n 1) (kth #f) (n-k 0) (qs xs) (ys xs) (zs (list)))
      (cond ((= k n) (if (null? ys) (error 'swap "k too big")
                       (loop1 (+ n 1) (car ys) 1 xs (cdr ys) (cons (car ys) zs))))
            ((pair? ys) (loop1 (+ n 1) kth (+ n-k 1) (cdr qs) (cdr ys) (cons (car ys) zs)))
            ((< n k) (error 'swap "k too big"))
            (else (let loop2 ((i 1) (zs zs) (ys (list)))
                    (cond ((= i k) (loop2 (+ i 1) (cdr zs) (cons kth ys)))
                          ((= i n-k) (loop2 (+ i 1) (cdr zs) (cons (car qs) ys)))
                          ((pair? zs) (loop2 (+ i 1) (cdr zs) (cons (car zs) ys)))
                          (else ys))))))))

Here’s some sample output:

> (swap 0 '(1 2 3 4 5 6 7))
Exception in swap: don't be silly
Type (debug) to enter the debugger.
> (swap 1 '(1 2 3 4 5 6 7))
(7 2 3 4 5 6 1)
> (swap 2 '(1 2 3 4 5 6 7))
(1 6 3 4 5 2 7)
> (swap 3 '(1 2 3 4 5 6 7))
(1 2 5 4 3 6 7)
> (swap 4 '(1 2 3 4 5 6 7))
(1 2 3 4 5 6 7)
> (swap 5 '(1 2 3 4 5 6 7))
(1 2 5 4 3 6 7)
> (swap 6 '(1 2 3 4 5 6 7))
(1 6 3 4 5 2 7)
> (swap 7 '(1 2 3 4 5 6 7))
(7 2 3 4 5 6 1)
> (swap 8 '(1 2 3 4 5 6 7))
Exception in swap: k too big
Type (debug) to enter the debugger.
> (swap 9 '(1 2 3 4 5 6 7))
Exception in swap: k too big
Type (debug) to enter the debugger.

Our code performs two passes over the data, one from front to back, the other from back to front. It is possible to solve the problem with a single pass over the data if you use mutation: find the two swap locations as in the front to back pass, then mutate the cars of the two locations:

(define (swap k xs)
  (if (< k 1) (error 'swap "don't be silly")
    (let loop ((n 1) (ps xs) (qs xs) (ys xs))
      (cond ((= k n) (if (null? ys) (error 'swap "k too big")
                       (loop (+ n 1) ys xs (cdr ys))))
            ((pair? ys) (loop (+ n 1) ps (cdr qs) (cdr ys)))
            ((< n k) (error 'swap "k too big"))
            (else (let ((t (car ps)))
                    (set-car! ps (car qs))
                    (set-car! qs t))
                  xs)))))

Here’s the same set of examples:

> (swap 0 '(1 2 3 4 5 6 7))
Exception in swap: don't be silly
Type (debug) to enter the debugger.
> (swap 1 '(1 2 3 4 5 6 7))
(7 2 3 4 5 6 1)
> (swap 2 '(1 2 3 4 5 6 7))
(1 6 3 4 5 2 7)
> (swap 3 '(1 2 3 4 5 6 7))
(1 2 5 4 3 6 7)
> (swap 4 '(1 2 3 4 5 6 7))
(1 2 3 4 5 6 7)
> (swap 5 '(1 2 3 4 5 6 7))
(1 2 5 4 3 6 7)
> (swap 6 '(1 2 3 4 5 6 7))
(1 6 3 4 5 2 7)
> (swap 7 '(1 2 3 4 5 6 7))
(7 2 3 4 5 6 1)
> (swap 8 '(1 2 3 4 5 6 7))
Exception in swap: k too big
Type (debug) to enter the debugger.
> (swap 9 '(1 2 3 4 5 6 7))
Exception in swap: k too big
Type (debug) to enter the debugger.

This is subtle code, easy to get wrong. But I was able to debug both versions in short order by printing values of the loop variables as I went. The debugging code is omitted above, but both code and debugging output are shown with the solution at http://ideone.com/KVSuXe.

As a primarily functional programmer, I tend not to think of solutions that require mutation, so a program like this is a good reminder that avoiding mutation has a cost: in this case, mutation saved a complete pass over the data and made the program much easier to write and maintain.

Advertisements

Pages: 1 2

4 Responses to “List Swap”

  1. Jussi Piitulainen said

    This does up to five O(n) scans, which is still O(n), and works (without special consideration) when an item is swapped with itself or when the position from the beginning is further in the list than the position from the end, and (accidentally) even when both positions are outside the list. The auxiliaries use 0-based indexing. The solution is 1-based as in the spec.

    (define (swap xs j k)
      (define (help xs j k)
        (lambda (a o)
          (cond
           ((= a j) (list-ref xs k))
           ((= a k) (list-ref xs j))
           (else o))))
      (map/index (help xs j k) xs))
    
    (define (map/index proc xs)
      (let loop ((k 0) (xs xs) (rs '()))
        (if (null? xs)
    	(reverse rs)
    	(loop (+ k 1) (cdr xs) (cons (proc k (car xs)) rs)))))
    
    (define (solution xs k) (swap xs (- k 1) (- (length xs) k)))
    
  2. matthew said

    It’s not difficult to do the swaps in place:

    #include <locale.h>
    #include <iostream>
    #include <algorithm>
    
    struct Cons {
      Cons(wchar_t v, Cons *n) : value(v), next(n) {}
      wchar_t value;
      Cons *next;
    };
    
    void swap(Cons *&root, int n) {
      // Create a pointer to the root
      Cons **p = &root;
      // Advance it n times
      for (int i = 0; i < n; i++) {
        p = &(*p)->next;
        // Return without change if list too short
        if (*p == 0) return;
      }
      // Now *p points at the first pointer cell to
      // be swapped.
      // q is another pointer to the root, r is the
      // list after the first n items, so the distance
      // between *q and r is n.
      Cons **q = &root, *r = *p;
      // Advance them in step until r gets to the end.
      while(true) {
        r = r->next;
        if (r == 0) break;
        q = &(*q)->next;
      }
      // Now *q points at the second pointer cell to be
      // swapped, so swap the pointers to the cells:
      std::swap(*p,*q);
      // and swap the rest pointers of the swapped cells:
      std::swap((*p)->next,(*q)->next);
    }
    
    void test(const wchar_t *s) {
      Cons *root = 0;
      int N = wcslen(s);
      for (int i = N; i > 0; i--) {
        root = new Cons(s[i-1],root);
      }
      for (int i = 0; i <= N; i++) {
        for (Cons *p = root; bool(p); p = p->next) {
          std::wcout << p->value;
        }
        std::wcout << "\n";
        swap(root,i);
      }
    }
    
    int main() {
      setlocale (LC_ALL, "");
      test(L"ⲀⲂⲄⲆⲈⲊ");
      test(L"𝀃𝀄𝀅𝀆𝀇𝀈𝀉"); 	
    }
    
    $ ./a.out
    ⲀⲂⲄⲆⲈⲊ
    ⲊⲂⲄⲆⲈⲀ
    ⲊⲈⲄⲆⲂⲀ
    ⲊⲈⲆⲄⲂⲀ
    ⲊⲈⲄⲆⲂⲀ
    ⲊⲂⲄⲆⲈⲀ
    ⲀⲂⲄⲆⲈⲊ
    𝀃𝀄𝀅𝀆𝀇𝀈𝀉
    𝀉𝀄𝀅𝀆𝀇𝀈𝀃
    𝀉𝀈𝀅𝀆𝀇𝀄𝀃
    𝀉𝀈𝀇𝀆𝀅𝀄𝀃
    𝀉𝀈𝀇𝀆𝀅𝀄𝀃
    𝀉𝀈𝀅𝀆𝀇𝀄𝀃
    𝀉𝀄𝀅𝀆𝀇𝀈𝀃
    𝀃𝀄𝀅𝀆𝀇𝀈𝀉
    
  3. kernelbob said

    It looks like my C solution is pretty similar to Matthew’s C++. There’s really only one way to do it in the C family…

    However, mine does detect cyclic lists and returns NULL for those.

    #include <assert.h>
    #include <stdbool.h>
    #include <stddef.h>
    #include <stdio.h>
    
    typedef struct node node;
    struct node {
        int value;
        node *link;
    };
    
    // Modify a linked list in place, exchanging the k'th elements from
    // the beginning and end of the list.
    //
    // The given example shows that k is one-based: the list starts with
    // item 1, not item 0.
    //
    // Returns the new head of list.
    // Returns NULL if list is shorter than k elements or is cyclic.
    
    node *list_swap(node *list, unsigned k)
    {
        if (!k)
            return NULL;            // EINVAL
        node **pp = &list;
        node **npp = pp;
        for (unsigned i = 0; i < k; i++) {
            if (!*npp)
                return NULL;        // fewer than k elements.
            pp = npp;
            npp = &(*pp)->link;
        }
        node **const pp0 = pp;      // k elements from beginning
        node **pp1 = &list;
        node *half = list;
        bool escapement = false;
        while (true) {
            pp = &(*pp)->link;
            if (*pp == NULL) {
                break;
            }
            pp1 = &(*pp1)->link;
            if (half == *pp)
                return NULL;        // cyclic list
            if (escapement)
                half = half->link;
            escapement = !escapement;
        }
    
        // Exchange *pp0 and *pp1.
        node *p0 = *pp0;
        node *p1 = *pp1;
        *pp1 = p0;
        *pp0 = p1;
        node *p0link = p0->link;
        p0->link = p1->link;
        p1->link = p0link;
    
        return list;
    }
    
    node *init_list(node arena[], size_t n)
    {
        for (int i = 0; i < n; i++) {
            arena[i].value = i + 1;
            arena[i].link = (i < n - 1) ? &arena[i + 1] : NULL;
        }
        return n ? arena : NULL;
    }
    
    void check_answer(node *head, node arena[], unsigned k, size_t n)
    {
        printf("{ ");
        int i = 0;
        for (node *p = head; p; p = p->link) {
            if (++i > 20) {
                printf("... ");
                break;
            }
            printf("%d ", p->value);
        }
        printf("}\n");
    
        #define SWIZ(i) (((i) + 1 == k) ? n - k : ((i) == n - k) ? k - 1 : i)
    
        for (size_t i = 0; i < n; i++) {
            size_t ip1 = SWIZ(i + 1);
            node *p = &arena[SWIZ(i)];
            node *next = (ip1 < n) ? &arena[ip1] : NULL;
            if (i == 0)
                assert(head == p);
            assert(p->value == i + 1 == k ? n - k + 1 : i == n - k ? k : i + 1);
            assert(p->link == next);
        }
    
        #undef SWIZ
    }
    
    int main()
    {
        node arena[7];
    
        // List lengths 0-7, 1 <= k <= n
        for (size_t n = 0; n <= 7; n++) {
            for (unsigned k = 1; k <= n; k++) {
                node *list = init_list(arena, n);
                node *l0 = list_swap(list, k);
                check_answer(l0, arena, k, n);
            }
            // Short list
            node *list = init_list(arena, n);
            assert(list_swap(list, n + 1) == NULL);
        }
    
        // Circular lists
        for (size_t i = 0; i < 7; i++) {
            for (unsigned k = 1; k <= 7; k++) {
                node *list = init_list(arena, 7);
                arena[6].link = &arena[i];
                assert(list_swap(list, k) == NULL);
            }
        }
    
        return 0;
    }
    

    Running it.

    $ cc list-swap.c && a.out
    { 1 }
    { 2 1 }
    { 2 1 }
    { 3 2 1 }
    { 1 2 3 }
    { 3 2 1 }
    { 4 2 3 1 }
    { 1 3 2 4 }
    { 1 3 2 4 }
    { 4 2 3 1 }
    { 5 2 3 4 1 }
    { 1 4 3 2 5 }
    { 1 2 3 4 5 }
    { 1 4 3 2 5 }
    { 5 2 3 4 1 }
    { 6 2 3 4 5 1 }
    { 1 5 3 4 2 6 }
    { 1 2 4 3 5 6 }
    { 1 2 4 3 5 6 }
    { 1 5 3 4 2 6 }
    { 6 2 3 4 5 1 }
    { 7 2 3 4 5 6 1 }
    { 1 6 3 4 5 2 7 }
    { 1 2 5 4 3 6 7 }
    { 1 2 3 4 5 6 7 }
    { 1 2 5 4 3 6 7 }
    { 1 6 3 4 5 2 7 }
    { 7 2 3 4 5 6 1 }

  4. matthew said

    @kernelbob: Pleased to be in good company. NIce point about circular lists. Here’s a version that should fix that (I don’t address the problem of freeing circular structures though). I’ve unrolled the loop once rather than use a flag variable:

    #include <locale.h>
    #include <assert.h>
    #include <iostream>
    #include <algorithm>
    
    struct Cons {
      Cons(wchar_t v, Cons *n) : value(v), next(n) {}
      wchar_t value;
      Cons *next;
    };
    
    bool swap(Cons *&root, int n) {
      // Create a pointer to the root
      Cons **p = &root;
      // Advance it n times
      for (int i = 0; i < n; i++) {
        p = &(*p)->next;
        // Return without change if list too short
        if (*p == 0) return false;
      }
      // Now *p points at the first pointer cell to
      // be swapped.
      // q is another pointer to the root, r is the
      // list after the first n items, so the distance
      // between *q and r is n.
      Cons **q = &root, *r = *p, *s = r;
      // Advance them in step until r gets to the end.
      while (true) {
        r = r->next;
        if (r == s) return false;
        if (r == 0) break;
        q = &(*q)->next;
        r = r->next;
        if (r == s) return false;
        if (r == 0) break;
        q = &(*q)->next;
        s = s->next;
      }
      // Now *q points at the second pointer cell to be
      // swapped, so swap the pointers to the cells:
      std::swap(*p,*q);
      // and swap the rest pointers of the swapped cells:
      std::swap((*p)->next,(*q)->next);
      return true;
    }
    
    void test(const wchar_t *s) {
      Cons *root = 0;
      int N = wcslen(s);
      for (int i = N; i > 0; i--) {
        root = new Cons(s[i-1],root);
      }
      for (int i = 0; ; i++) {
        for (Cons *p = root; bool(p); p = p->next) {
          std::wcout << p->value;
        }
        std::wcout << "\n";
        if (!swap(root,i)) break;
      }
      Cons *last = root;
      while (last->next) last = last->next;
      for (int i = 0; i < N; i++) {
        Cons *p = root;
        for (int j = 0; j < i; j++) p = p->next;
        last->next = p;
        assert(!swap(root,2*N));
      }
    }
    
    int main() {
      setlocale (LC_ALL, "");
      test(L"①②③④⑤⑥");
      test(L"☿♀♁♂♃♄♅♆♇");
    }
    
    ①②③④⑤⑥
    ⑥②③④⑤①
    ⑥⑤③④②①
    ⑥⑤④③②①
    ⑥⑤③④②①
    ⑥②③④⑤①
    ①②③④⑤⑥
    ☿♀♁♂♃♄♅♆♇
    ♇♀♁♂♃♄♅♆☿
    ♇♆♁♂♃♄♅♀☿
    ♇♆♅♂♃♄♁♀☿
    ♇♆♅♄♃♂♁♀☿
    ♇♆♅♄♃♂♁♀☿
    ♇♆♅♂♃♄♁♀☿
    ♇♆♁♂♃♄♅♀☿
    ♇♀♁♂♃♄♅♆☿
    ☿♀♁♂♃♄♅♆♇
    

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

%d bloggers like this: