CODEWITHSUNDEEP
pythonalgorithmgreedy
Larynx
Larynx

Reputation: 408

GreedySorting in python

I'm defining a Python function which execute the greedy sorting.
(Bioinformatics Algorithms I, 2014, Coursera - Stepic 6.4)

The result of sorting should be [+1, +2, +3, +4, +5] and the function should return all the steps of changes from initial input list, too.

To sort initial input list, several steps of reversal are essential. It is much like pancake flipping problem. In this question, signed permutation ([-3,+4,+1,+5,-2]) should be changed to identity signed permutation ([+1, +2, +3, +4, +5]).

Sample Input: 

 [-3, +4, +1, +5, -2]

Sample Output: 

[[-1, -4, +3, +5, -2],    
 [+1, -4, +3, +5, -2],    # -1  ->  +1
 [+1, +2, -5, -3, +4],    # reversal of (-4, +3, +5, -2)
 [+1, +2, +3, +5, +4],    # reversal of (-5, -3)
 [+1, +2, +3, -4, -5],    # reversal of (+5, +4)
 [+1, +2, +3, +4, -5],    # -4  ->  +4  
 [+1, +2, +3, +4, +5]]    # -5  ->  +5   Sorting finished!

I wrote a function but it's result was not correct.

# Implementation
def reversing(seq):
    """
    >>> reversing([+1,+2,-3,-4])
        [+4,+3,-2,-1]
    """
    seq.reverse()
    seq = map(lambda(x): -x, seq)
    return seq


def greedySorting1(lst):
    """
    ApproxReversalDistance (ARD)
    Return a number (ARD) until the result is [1,2,...,n]
    >>> greedySorting1([1,-5,3,-2,-4])
        6
    """
    change = []
    ARD = 0

    for i in range(len(lst)):
        if lst[i] != i+1:
            if i+1 in lst:
                id_i = lst.index(abs(i+1)) 
            else:
                id_i = lst.index(-abs(i+1))
            lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]
            ARD += 1
            change.append(lst)
        if lst[i] == -(i+1):
            lst[i] = i+1
            ARD += 1
            change.append(lst)

    return change   




# Testing
print greedySorting([-3,+4,+1,+5,-2])

    [[+1, -4, +3, +5, -2],    # Wrong: +1 should be -1
     [+1, -4, +3, +5, -2], 
     [+1, +2, -5, -3, +4], 
     [+1, +2, +3, +5, +4], 
     [+1, +2, +3, +4, -5],    # Wrong: +4 should be -4
     [+1, +2, +3, +4, -5], 
     [+1, +2, +3, +4, +5]]

How can I fix my code to get correct answer like sample output?
Thanks.

Upvotes: 1

Views: 2153

Answers (2)

John La Rooy
John La Rooy

Reputation: 304205

Here you are modifying lst in-place, so any references to it in change will reflect that same change

if lst[i] == -(i+1):

You can make sure to "decouple" the lists in change by using lst[:] to make a copy

for i in range(len(lst)):
    if lst[i] != i+1:
        if i+1 in lst:
            id_i = lst.index(abs(i+1)) 
        else:
            id_i = lst.index(-abs(i+1))
        lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]
        ARD += 1
        change.append(lst[:])
    if lst[i] == -(i+1):
        lst[i] = i+1
        change.append(lst[:])

Now you can also simplify this line:

lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]

to

lst[i: id_i + 1] = reversing(lst[i: id_i + 1])

Upvotes: 2

Adam
Adam

Reputation: 55

When I solved this problem, I found it much easier to solve with the signs and numbers in two, matched index arrays, and making a copy of the list and the signs on each iteration to use as a reference (doesn't hurt as much as you think in terms of runtime/memory alloc.

One more thing that will help you is to use a nested for loop, to help you keep track of the switching of the numbers and signs inside the "reversal".

Upvotes: 1

Related Questions