One-Swappable Array

July 24, 2015

Today’s exercise helps somebody with their homework:

Given an array of unique integers, determine if it is possible to sort the array by swapping two elements of the array. For instance, the array [1,2,6,4,5,3,7] can be sorted by swapping 3 and 6, but there is no way to sort the array [5,4,3,2,1] by swapping two of its elements. You may use O(n) time, where the array has n integers, and constant additional space.

Your task is to write a program that determines if an array can be sorted with a single swap. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

9 Responses to “One-Swappable Array”

  1. Paul said

    In Python.

    def test(seq):
        """returns True if already sorted,
                   indexes if a swap makes the array sorted
                   False otherwise
        """
        n = len(seq)
        i, j = 0, n - 1
        while i < j and seq[i] < seq[i + 1]: i += 1
        while i < j and seq[j] > seq[j - 1]: j -= 1
        if i == j: return True
        ic, jc = i, j
        seq[i], seq[j] = seq[j], seq[i]
        i, j = max(i - 1, 0), min(j + 1, n - 1)
        while i < j and seq[i] < seq[i + 1]: i += 1
        while i < j and seq[j] > seq[j - 1]: j -= 1
        if i == j: return ic, jc
        return False
    
  2. Jussi Piitulainen said

    Objection to the modification of the input array. This was supposed to be only a test.

    I convinced myself that there have to be one or two pairs of adjacent numbers that are out of order, and those need to be compared to the numbers that are adjacent to them. To manage the complexity, I created a sort of a generator object, and a filter on it, and requested the first, second, and third such quadruple (a quadruple false when not available). Then the test was easy to write. Three linear scans over the input (two of them to find min and max), constant space for state in the generator, and multiple values should be passed without heap allocation in a quality implementation.

    Today I’m telling the sourcecode processor that Scheme is “delphi”.

    (define (fold o e s) (if (null? s) e (fold o (o e (car s)) (cdr s))))
    
    (define (windows s) ; generate adjacent pairs with sentinels                                                     
      (let ((less (fold min (car s) (cdr s)))
            (more (fold max (car s) (cdr s))))
        (let ((x (car s))
              (s (cdr s)))
          (lambda ()
            (if (null? s)
                (values #f #f #f #f)
                (let ((a less)
                      (b x)
                      (c (car s))
                      (d (if (null? (cdr s)) more (cadr s))))
                  (set! less x)
                  (set! x c)
                  (set! s (cdr s))
                  (values a b c d)))))))
    
    (define (derangements gen) ; filter out non-derangements                                                         
      (lambda ()
        (call-with-values
            gen
          (lambda (a b c d)
            (if (and a b c d (< b c))
                ((derangements gen))
                (values a b c d))))))
    
    (define (swappable? s)
      (and (pair? s) ; needed to have min and max for sentinels                                                      
           (let ((gen (derangements (windows s))))
             (call-with-values ; this cascade is a let* on gen                                                       
                 gen
               (lambda (a b c d)
                 (call-with-values
                     gen
                   (lambda (p q r s)
                     (call-with-values
                         gen
                       (lambda (x y z w)
                         (and b       ; at least one derangement                                                     
                              (not y) ; at most two derangements                                                     
                              (if (not q) ; one?                                                                     
                                  (<= a c b d) ; one: swap adjacent                                                  
                                  (<= a r c q b s))))))))))))
    

    I tested with the following.

    (for-each
     (lambda (s)
       (display s)
       (display (if (swappable? s) " is swappable" " is not swappable"))
       (newline))
     (list '() '(3) '(3 7) '(7 3)
           '(1 3 7) '(3 1 7) '(3 7 1) '(7 1 3) '(7 3 1)
           '(1 2 6 4 5 3 7) '(1 2 3 4 6 5 7)
           '(1 2 3 4 5 7 6) '(2 1 3 4 5 6 7)
           '(5 4 3 2 1)))
    

    I got the following response.

    () is not swappable
    (3) is not swappable
    (3 7) is not swappable
    (7 3) is swappable
    (1 3 7) is not swappable
    (3 1 7) is swappable
    (3 7 1) is not swappable
    (7 1 3) is not swappable
    (7 3 1) is swappable
    (1 2 6 4 5 3 7) is swappable
    (1 2 3 4 6 5 7) is swappable
    (1 2 3 4 5 7 6) is swappable
    (2 1 3 4 5 6 7) is swappable
    (5 4 3 2 1) is not swappable
    
  3. Jussi Piitulainen said

    Oops, I noticed that my derangements filter creates a new short-lived procedure for each window. That may or may not violate the constant-space requirement. I prefer to think it doesn’t, as that memory is immediately reclaimable.

  4. Mike said

    Python solution.
    Scan the list to find indexes where the items are out of order. If there are only two, check to see if swapping the two items would place the list in order. Special case if one of the items is first or last in the list.

    def is_one_swap(lst):
        index = [i for i in range(len(lst) - 1) if lst[i] > lst[i+1]]
    
        if len(index) == 2:
            i, j = index[0], index[1] + 1
    
            return (    (    (i == 0 or lst[i-1] <= lst[j])
                         and lst[j] <= lst[i+1])
                    and (    lst[j-1] <= lst[i] 
                         and (j == len(lst)-1 or lst[i] <= lst[j+1])))
        
        return False
    
    #tests
    def swapped(lst, i, j):
        return lst[:i] + lst[j:j+1] + lst[i+1:j] + lst[i:i+1] + lst[j+1:]
        
    x = list(range(1,8))
    y = swapped(x, 0, 4); print(y, is_one_swap(y))
    y = swapped(x, 4, 6); print(y, is_one_swap(y))
    y = swapped(x, 2, 4); print(y, is_one_swap(y))
    
    y = x                                                 ; print(y, is_one_swap(y))
    y = swapped(swapped(x, 2, 4), 0, 3); print(y, is_one_swap(y))
    
  5. Mike said

    My solution had a bug: two element arrays that are one-swappable are not handled correctly..
    Here is a solution with at least one less bug.

    def is_one_swap(lst):
        index = [i for i in range(len(lst) - 1) if lst[i] > lst[i+1]]
    
        if len(index) == 2 or len(index) == 1 and len(lst) == 2:
            i, j = index[0], index[-1] + 1
    
            return (    (    (i == 0 or lst[i-1] <= lst[j])
                         and lst[j] <= lst[i+1])
                    and (    lst[j-1] <= lst[i] 
                         and (j == len(lst)-1 or lst[i] <= lst[j+1])))
        
        return False
    
    #tests
    def swapped(lst, i, j):
        return lst[:i] + lst[j:j+1] + lst[i+1:j] + lst[i:i+1] + lst[j+1:]
        
    x = list(range(1,8))
    y = swapped(x, 0, 4); print(y, is_one_swap(y))
    y = swapped(x, 4, 6); print(y, is_one_swap(y))
    y = swapped(x, 2, 4); print(y, is_one_swap(y))
    y = [99, 0]                        ; print(y, is_one_swap(y))
    
    y = []                             ; print(y, is_one_swap(y))
    y = [42]                           ; print(y, is_one_swap(y))
    y = [42, 99]                       ; print(y, is_one_swap(y))
    y = x                              ; print(y, is_one_swap(y))
    y = swapped(swapped(x, 2, 4), 0, 3); print(y, is_one_swap(y))
    
    y = x[:]; y[3] = 6; print(y, is_one_swap(y))
    
    
  6. Jussi Piitulainen said

    Mike, your index takes O(n) space. Consider a reversed range, for example.

    index = [i for i in range(len(lst) - 1) if lst[i] > lst[i+1]]
    

    Use a generator expression instead of the list comprehension and only request up to one too many index elements. I haven’t exactly tested the following.

    finder = ([i] for i in range(len(lst) - 1) if lst[i] > lst[i+1])
    index = next(finder, []) + next(finder, []) + next(finder, [])
    

    Also, there can be only one index element whenever the swapped integers are adjacent in the list.

  7. Paul said

    A shorter version in Python. Basically the same as my first version, but here generators are used are used for looping. For testing I started to use hypothesis, which makes it easy to generate a lot of test cases. I think I like it.

    def swappable(seq):
        seq = list(seq)
        n = len(seq)
        if n == 0: return False
        ic = next((i for i in range(n-1) if seq[i] > seq[i+1]), None)
        if ic is None: return False # already sorted
        jc = next(i for i in range(n-1, ic, -1) if seq[i] < seq[i-1])
        seq[ic], seq[jc] = seq[jc], seq[ic]
        return all(seq[i] < seq[i+1] for i in range(max(ic-1, 0), min(jc+2, n-1))) and (ic, jc) 
    
  8. Mike said

    New and improved:

    import itertools as it
    
    def is_one_swap(lst):
        index = list(it.islice((i for i in range(len(lst) - 1) if lst[i] > lst[i+1]), 3))
        
        if 1 <= len(index) <= 2:
            i, j, e = index[0], index[-1] + 1, len(lst) - 1
            if (    (i == 0 and lst[j] <= lst[i+1] or lst[i-1] <= lst[j] <= lst[i+1]) 
                and (j == e and lst[j-1] <= lst[i] or lst[j-1] <= lst[i] <= lst[j+1])):
                    return i, j
        return None, None
    
  9. […] One-swap sorting problem in common lisp. […]

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: