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

Comments

These comments are moderated. Your comment will not be visible unless accepted by the content owner.

Only simple HTML formatting is allowed and any hyperlinks will be stripped away. If you need to include a URL then please simply type it so that users can copy and paste it if needed.

(Required)

(Required)