Prev - #37 Change Maker | Table of Contents | Next - #39 Collatz Sequence
Exercise #38: Random Shuffleshuffle([1, 2, 3, 4, 5]) → [3, 1, 4, 5, 2]
A random shuffle algorithm puts the values in a list into a random order, like shuffling a deck of cards. This algorithm produces a new permutation, or ordering, of the values in the list. The algorithm works by looping over each value in the list and randomly determining a new index with which to swap it. As a result, the values in the list are in random order.
For a list of n values, there are n! (“n factorial”) possible permutations. For example, a 10-value list has 10! or 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 or 3,628,800 possible ways to order them.
This exercise modifies the list passed to it in-place, rather than creating a new list and returning it. Because lists are mutable objects in Python, modifications made to a parameter are actually modifying the original object passed to the function call for that parameter. For example, enter the following into the interactive shell:
>>> someList = [1, 2, 3]
>>> def someFunc(someParam):
... someParam[0] = 'dog'
... someParam.append('xyz')
...
>>> someList
[1, 2, 3]
>>> someFunc(someList)
>>> someList
['dog', 2, 3, 'xyz']
Notice that the someList list is passed as the argument for the someParam parameter of the someFunc() function. This function modifies someParam (which refers to the same list object that the someList variable refers to), so these modifications are still there after the function returns. The someFunc() function isn’t returning a new list to replace someList; it’s modifying someList in-place.
In Python, only mutable objects (such as lists, dictionaries, and sets) can be modified in-place. Immutable objects (such a strings, integers, tuples, and frozen sets) can’t be modified in-place.
Exercise Description
Write a shuffle() function with a values parameter set to a list of values. The function doesn’t return anything, but rather it sets each value in the list to a random index. The resulting shuffled list must contain the same values as before but in random order.
This exercise asks you to implement a function identical to Python’s random.shuffle() function. As such, avoid using this function in your solution as it’d defeat the purpose of the exercise.
These Python assert statements stop the program if their condition is False. Copy them to the bottom of your solution program. Your solution is correct if the following assert statements’ conditions are all True:
random.seed(42)
for i in range(10):
testData1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
shuffle(testData1)
assert len(testData1) == 10
assert testData1 != [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
assert sorted(testData1) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
testData2 = []
shuffle(testData2)
assert testData2 == []
Try to write a solution based on the information in this description. If you still have trouble solving this exercise, read the Solution Design and Special Cases and Gotchas sections for additional hints.
Prerequisite concepts: import statements, random module, randint(), for loops, range(), len(), swapping values
Solution Design
The solution is surprisingly straightforward. A for loop can loop over every index in the list. On each iteration, the code in the loop selects a random index. Then it swaps the values at the current iteration’s index and the random index.
If the random index is the same as the current iteration’s index, this is fine: a random shuffling can include values at their original location. This isn’t somehow “less random” than any other permutation. If the random index is a repeat of an index that has previously been swapped, this is fine as well. Shuffling a value to a random location twice isn’t any more or less shuffled than moving a value to a random location once.
Special Cases and Gotchas
Take care that your shuffle() function doesn’t add or remove any values to the list; it should only rearrange the values already in the list. Because the shuffle() function modifies the values list argument in-place, it doesn’t need to return anything. There shouldn’t be a return statement anywhere in the function. In Python, all functions technically return a value; it’s just that functions with no return statement return the value None.
When selecting a random index, select only an index within the range of the list’s indexes. This means you should select an index from 0 up to, but not including, the length of the list. When calling random.randint() to generate this random index, you’ll want to use 0 and len(values) - 1 to represent this range, and not 0 and len(values).
Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.
Solution Template
Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/randomshuffle-template.py and paste it into your code editor. Replace the underscores with code to make a working program:
import random
def shuffle(values):
for i in range(____(values)):
swapIndex = random.randint(0, len(____) - ____)
values[i], values[swapIndex] = values[____], values[____]
The complete solution for this exercise is given in Appendix A and https://invpy.com/randomshuffle.py. You can view each step of this program as it runs under a debugger at https://invpy.com/randomshuffle-debug/.
Prev - #37 Change Maker | Table of Contents | Next - #39 Collatz Sequence
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4