Python: check if a list can be sorted by swapping two elements, only one swap is allowed

Question

Here in below code, I'm trying to find out if there are two elements in left side which are greater than right side element but this doesn't seem to work for my problem. Any hints to write further logic? I'm stuck here.

swap.py

def swap(lst):
    count = 0
    for k in range(0, len(lst)-1):
        if lst[k] > lst[k+1]:
            count += 1
    if int(count) == 2:
        print "Swapped"
    elif int(count) == 0:
        print True
    else:
        print False


if __name__ == "__main__":
    swap([1,2,3,4,0])
    swap([6,4,2,5])
    swap([6,4,2,8])
    swap([1,4,5])

My expected output from program -

[1,4,5] will return True
[6,4,2,8] will return Swapped
[6,4,2,5] will return False

What exactly is 'swapped'? Are you checking if swapping two elements will sort your list? — Patrick Haugh, Nov 16 '16 at 19:59
yes I'm just checking, if by swapping only two elements, the list will be sorted if yes then I'm printing a string "swapped" — Sanchit, Nov 16 '16 at 20:00
Look at the algorithm presented in the answer here and try to implement it: http://stackoverflow.com/questions/29999113/javascript-check-if-list-is-sorted-after-one-swap — Patrick Haugh, Nov 16 '16 at 20:15
This might be unacceptable as a solution, but I believe it would be easier to actually sort the list and then check if you can get from there to the original list with just one swap. — frnhr, Nov 19 '16 at 20:44

score 1 · Answer 1 · answered Nov 16 '16 at 20:12

from itertools import combinations
def is_swappable(lst):
    s = sorted(lst)
    for i, j in combinations(range(len(lst)), 2):
        l = lst[:]
        l[i], l[j] = l[j], l[i]
        if l == s:
            return True
    return False

Here's a pretty naive solution. Tries swapping every pair in the list and sees if that results in the sorted list.

score 0 · Answer 2 · answered Apr 07 '22 at 16:48

I did not understand the "swapped" condition but the following code snipped will tell you if you can sort an array in one swap or not. Code is written in Python 3 and the complexity of this code is O(nlog(n))

def checkOneSwap(arr):
    N = len(arr)
    if N <= 2:
        print(True)

    arr2 = []
    for index in range(N):
        arr2.append(arr[index])
    arr2.sort()
    counter = 0
    for i in range(N):
        if arr[i] != arr2[i]:
            counter += 1

    if counter == 0 or counter == 2:
        print(True)
    else:
        print(False)

checkOneSwap([1,2,3,4,0])   # False    you definetly need for than 2 swap to make this array sorted
checkOneSwap([6,4,2,5])     # False    [2,4,5,6] -> swap(6,2) and then swap(6,5) require 2 swap to make this array sorted 
checkOneSwap([6,4,2,8])     # True     [2,4,6,8] -> swap(6,2), one swap required to make this array sorted
checkOneSwap([1,4,5])       # True     [1,4,5]  -> already sorted,counter = 0

hightower · Answer 3 · 2022-09-14T11:06:44.937

0

Can be done with for loop, but I prefer list comprehension. Zip sorted and unsorted list and create a list of mismatches. If the length of mismatches is more than 2, then you can't sort in 1 swap.

def is_sortable_by_one_swap(unsorted_list):
    mismatches = [x for x in zip(unsorted_list, sorted(unsorted_list)) if x[0] != x[1]]
    return len(mismatches) <= 2

edited Sep 14 '22 at 11:06

answered May 19 '22 at 15:32

hightower

31
4

Python: check if a list can be sorted by swapping two elements, only one swap is allowed

3 Answers3