Landing : Athabascau University

COMP200 - Shuffle Left Algorithm

So, I've been learning about Computer Science and my textbook likes to throw these algorithms at me. I thought to myself, "self, you should implement these instructions into something usable." and so I did.

You can download the py file from [here] but I'll post the text anyway.


## utf-8
"""
## shuffle left Algorithm ##
1  Get values for n and the n data items
2  Set the value of legit to n
3  Set the value of left to 1
4  Set the value of right to 2
5  While left is less than or equal to legit do Steps 6 through 14
6    If the item at position left is not 0 then do Steps 7 and 8
7      Increase left by 1
8      Increase right by 1
9    Else (the item at position left is 0) do Steps 10 through 14
10     Reduce legit by 1
11     While right is less than or equal to n do Steps 12 and 13
12       Copy the item at position right into position (right − 1)
13       Increase right by 1
14     Set the value of right to (left + 1)
15  stop

 (Schneider p117)
Schneider, G. M., Judith Gersting. Invitation to Computer Science,  6th Edition.
Cengage/Nelson, 01/2012.
"""

def shuffleLeft(data, verbose=False):
    """ (list of integers) --> list of integers with no 0's
    using the shuffle left Algorithm """

    n = len(data)
    #2 Set the value of legit to n
    legit = n
    #3 Set the value of left to 1
    left = 0 ## positions start at 0 not 1
    #4 Set the value of right to 2
    right = 1 ## positions start at 0 not 1

    #5  While left is less than or equal to legit do Steps 6 through 14
    while left < legit: ## positions start at 0 not 1
        #6 If the item at position left is not 0 then do Steps 7 and 8
        if data[left] != 0:
            #7 Increase left by 1
            left += 1
            #8 Increase right by 1
            right += 1
        #9 Else (the item at position left is 0) do Steps 10 through 14
        else:
            #10 Reduce legit by 1
            legit -= 1
            #11 While right is less than or equal to n do Steps 12 and 13
            while right <= legit:
                #12 Copy the item at position right into position (right − 1)
                data[right-1] = data[right]
                #13 Increase right by 1
                right += 1
            data = data[0 : legit]
        if verbose:
            print("%s - %s - %s" % (legit == len(data), legit, data))
        #14 Set the value of right to (left + 1)
        right = left + 1
    #15 Stop


if __name__ == "__main__":
    dataset = [
               [1, 0, 24, 16, 0, 36, 42, 23, 21, 0],
               [16, 35, 0, 0, 54, 0, 8, 12, 0, 6, 0, 4, 0, 3, 0, 6, 0, 9, 0],
               [0, 24, 1, 2, 32, 98, 56, 45, 21, 0, 0, 21, 35, 35, 0]
               ]
    for testlist in dataset:
        shuffleLeft(testlist, verbose=True)


comments are welcome
~ Friar Greg




Original: https://friargreg.blogspot.com/2019/01/comp200-shuffle-left-algorithm.html
By: Greg Denyes
Posted: January 4, 2019, 10:26 pm