3: - A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 2 (for True Epub) - Jay Wengrow - RutLib.com

Chapter 3

These are the solutions to the .

Here’s one possible approach, which randomly selects 3 indexes from the array and returns the values at those indexes.

	import random


	def pick_3(array):
	chosen_indexes = []

	for _ in range(3):
	random_index = random.randint(0, len(array) - 1)
	while random_index in chosen_indexes:
	random_index = random.randint(0, len(array) - 1)

	chosen_indexes.append(random_index)

	# sort the indexes to ensure we return the values
	# in their original order:
	chosen_indexes.sort()

	chosen_values = []
	for index in chosen_indexes:
	chosen_values.append(array[index])

	return chosen_values

Here, we grab all the hash table’s keys(), convert the result into an array with the list keyword, and then use random.choice to pick one random item from the array:
import random

def sample(hash_table):
return random.choice(list(hash_table.keys()))

Let’s say that we’re selecting a single random value from the array ["a", "b", "c", "d", "e", "f", "g"]. Our first iteration of the loop will point to the "a" and decide whether it’s the value to select. The question is: how can we ensure that this "a" has an equal chance of being selected as each other value in the array?

Now, because there are 7 values, this means that each value should have a 1/7 chance in being selected. And so, to decide if we’re going to select the "a", we should roll a 7-sided die, and if the die lands on one particular side, we’ll select the "a". If the die lands on any of the other 6 sides, we will not select the "a".

In code, this would look something like roll = random.randint(1, 7), which chooses a random integer from 1 to 7, inclusive. We can decide that if the result is a 1, we’ll select the "a", and if the result is some other number, we’ll move on to the next iteration of the loop.

Now, in the next iteration of the loop, the current value is "b". How do we give "b" an equal opportunity of being the chosen value? Like every other value, we want to ensure that the "b" also has a 1/7 chance of being selected.

Intuitively, we may think that we should roll another 7-sided die to see whether we’ll choose the "b". However, this is not the right move to make, and here’s why.

The "a" already got its day in the sun—that is, we already gave it a fair chance at being selected. Once the "a" was not selected, it no longer has any bearing on whether we should choose the "b". And so, when we are deciding whether to select "b", we need to give the "b" the same odds as every other value that we haven’t iterated over yet, namely, "c", "d", "e", "f", and "g".

In other words, with "a" out of the way, we’re now deciding whether, of the 6 values that remain, we should select the "b". Therefore, we want to give the "b" a 1/6 chance of being chosen. And so, we can run roll = random.randint(1, 6) and select the "b" if the roll turns out to be 1.

To make this even more intuitive, I’ll explain this from yet another angle. Imagine that we’re randomly selecting a value from an array that only contains 2 values, such as ["a", "b"]. Say that we gave the "a" a 1/2 chance of being chosen, and it wasn’t selected. At this point, we should simply select the "b" instead. The "a" lost its 50 percent chance, so we select the "b" instead.

If we were to instead roll the die again to see whether we select the "b", the "b" will ultimately only have a 1/4 chance of being selected since 1/2 * 1/2 = 1/4. Additionally, if the "b" loses on its roll, we won’t end up selecting anything from the array!

Similarly, with the case of ["a", "b", "c", "d", "e", "f", "g"], if we rolled a 7-sided die for "a" and do the same again for "b", it would come out that the "b" has a 6/49 chance of being selected. That is, for the "b" to be selected, it relies on the 6/7 chance that the "a" will not be selected. When we multiply that 6/7 chance by the 1/7 that "b" will be selected, that produces a chance of 6/49. The odds of 6/49 are slightly less than the 1/7 we were aiming for.

So instead, we roll a 6-sided die for the "b". This way, when we multiply the 6/7 chance that the "a" is not selected by the 1/6 chance that the "b" is selected, we get: 6/7 * 1/6 = 6/42, which is the same as 1/7.

As we proceed through each value in the array, we reduce the “sides of the die” by 1. So on the next round, we’ll roll a 5-sided die, and on the next round a 4-sided die, and so on.

If the first 6 values are not selected, we automatically select the final value, the "g". The "g" relies on the 6/7 chance that the "a" isn’t selected, multiplied by the 5/6 chance that the "b" isn’t selected, multiplied by the 4/5 chance that the "c" isn’t selected, and so on.

This gives us:

6/7 * 5/6 * 4/5 * 3/4 * 2/3 * 1/2 = 1/7. Tada!

Here is the code:

	import random


	def sample(array):
	denominator = len(array)

	for value in array[:-1]:
	roll = random.randint(1, denominator)

	if roll == 1:
	return value

	denominator -= 1

	return array[-1]

This solution builds upon the previous one. The gist of the algorithm goes like this:

We begin to traverse the tree, starting at the root node. We’ll use the variable current_node to refer to whichever node we’re pointing to at a given moment.
We always keep track of how many nodes are contained in the subtree of which the current_node is the “root.” We’ll call this variable the subtree_size. (At the beginning of our algorithm, when current_node is the true root, the subtree_size will indeed be the size of the entire tree.) Since we know that the tree is complete, we can compute the subtree_size based on how many levels the tree has rather than traverse the entire tree and count all the nodes. See the tree_size method to follow for the exact calculation.
We roll a die from 1 up to the subtree_size. If the die lands on 1, we select the current_node as our winning node. If, for example, the subtree contains 15 nodes, this gives the current node a 1/15 chance of being chosen. This is exactly what we want since we want to give each of the 15 nodes of the tree an equal chance of being chosen as the winner.
If our die does not land on 1, then we continue to traverse the tree by moving down to the current_node’s child. To decide whether we’ll select the left child or the right child, we roll a die. If it lands on 1, we move left, and if it lands on 2, we move right. This way, both the left descendants and the right descendants of the current_node have an equal chance of eventually becoming the winner. Whichever child we end up choosing becomes the new current_node.
We now calculate how many nodes are contained in the subtree of the new current_node. Since each time we move down a level in a binary tree, we exclude half of the remaining nodes from our traversal path, we simply divide the old subtree_size by 2. (We use floor division, so if the previous subtree had 15 nodes, the current subtree now has 7 nodes. This floor division works since we also have to exclude the previous current_node itself, in addition to the other half of its descendants.)
We start over again at Step “c.” That is, we now roll a die from 1 up to the new subtree_size. If we roll a 1, the new current_node is the winner; otherwise, we move on again. If we eventually reach a leaf node, the subtree_size will be 1, in which case the leaf node will definitely be selected as the winner.

Here’s the code, including a simple implementation of a BST:

	import random


	class TreeNode:
	def __init__(self, value, left=None, right=None):
	self.value = value
	self.left_child = left
	self.right_child = right


	def insert(value, node):
	if value < node.value:

	if not node.left_child:
	node.left_child = TreeNode(value)
	else:
	insert(value, node.left_child)

	elif value > node.value:

	if not node.right_child:
	node.right_child = TreeNode(value)
	else:
	insert(value, node.right_child)


	def tree_size(node):
	level_size = 1
	total_size = 1

	current_node = node.left_child
	while current_node:
	level_size *= 2
	total_size += level_size
	current_node = current_node.left_child

	return total_size


	def sample(node):
	subtree_size = tree_size(node)
	current_node = node

	while current_node:
	roll = random.randint(1, subtree_size)
	if roll == 1:
	return current_node.value

	subtree_size //= 2

	roll = random.randint(1, 2)
	if roll == 1:
	current_node = current_node.left_child
	else:
	current_node = current_node.right_child

The primary algorithm here takes place in the sample method. You’ll see, though, that it relies on a tree_size method to calculate the size of the entire tree. Again, this calculation is only valid if the tree is complete. Otherwise, you may have to traverse the entire tree and simply count up all the nodes.

	import random


	def sample(hash_table):
	return random.choice(list(hash_table.keys()))