7. Generators and Recursion#
Write a function to generate the length 2 combinations for the elements of a list.
One way to think about this is as a matrix. Suppose we have a list \([i_0, i_1, \dots, i_{n-1}]\). Write out each permutation of pairs (with replacement) as a matrix.
The matrix contains all possible permutations (with replacement). The matrix is symmetric meaning for each pair \((i_a, i_b)\) below the diagonal, the pair \((i_b, i_a)\) is above the diagonal. This means the set of combination pairs for our list is above the diagonal. Therefore, we only have to generate the pairs above the diagonal.
Here is another way of saying this. Suppose again we have a list \(i = [i_0, i_1, \dots, i_{n-1}]\). Suppose we generate all the permutations that start with \(i_a\) for \(a=0, 1, \dots, b - 1\) where \(b \leq n - 1\). Then, for the list of permutations that start with \(i_b\), then \((i_j, i_b)\) has already been generated if \(j < b\).
Let us write our function to generate combinations.
>>> def combinations(items):
... for i, first_item in enumerate(items):
... for second_item in items[i + 1:]:
... yield first_item, second_item
>>> [i for i in combinations([1, 2, 3, 4, 5])]
>>> [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
What about the case where \(r=3\). Let us try extending the rule we defined above and used it for the case where \(r=3\).
>>> def combinations(items):
... for i, first_item in enumerate(items[:-2]):
... for j, second_item in enumerate(items[i + 1:-1]):
... for third_item in items[i + j + 2:]:
... yield first_item, second_item, third_item
>>> [i for i in combinations([1, 2, 3, 4, 5])]
>>> [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
The nested for loops are already getting quite deep. This will only get worse
as we increase r. One way to deal with this is by using recursion. We
will talk about this later but for now we will discuss how we arrived at a
solution for r=3 and potentially any value r.
7.1. Generating combinations of length 3#
For generating the combinations of length 2, we were able to create a matrix of
permutations and see that everything along the diagonal could be ignored and
any combination below the diagonal was repeated above the diagonal. This let us
limit our generating to only the upper diagonal elements making our life a
little easier. For the case where r=3 creating a matrix is not as
simple.
For the r=2 case, the rows of the matrix represented the index of the
first element and the columns represented the rows of the second element in the
combinations. We may be able to use a similar matrix representation using a 3D
starts getting complicated; The complexity only increases as r
increases?
What can we gain from the matrix representation for r=2 that could be
applied to r=3? First recall the matrix representation for r=2.
Clearly, the combinations below the diagonal are repeated since the matrix is symmetric. Another way of expressing this is the set length 2 combinations is the set of combinations \((i_a, i_b)\) where \(b < a\).
Extending this to the length 3 case, we can say the set of length 3 combinations is the set of permutations \((i_a, i_b, i_c)\) where \(a < b < c\). We can prove this by contradiction. Suppose we have the set of all combinations, \((i_a, i_b, i_c)\), where \(i_a < i_b < i_c\). Suppose there is another combination \((i_{a^*}, i_{b^*}, i_{c^*})\) that is not in our existing list of ordered combinations. We can reorder (i_{a^*}, i_{b^*}, i_{c^*}) to make it satisfy the inequality and by our initial assumption, (i_{a^*}, i_{b^*}, i_{c^*}) is already in our list of combinations.
So, we can represent every combination of length 3 as a tuple, \((i_a, i_b, i_c)\), such that \(i_a < i_b < i_c\). Keeping that in mind, let us generate the length three combinations of \([1, 2, 3, 4]\).
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
The above combinations all satisfy \(i_a < i_b < i_c\). The combinations
were generated by starting with the minimum combination, [1, 2, 3]
then incrementing the item furthest on the right until it hits the maximum
value.
We now have a basic outline for an algorithm for generating the combinations. Let us write some code using recursion to perform this algorithm.
def combinations(items, r):
combination_store = [None] * r
length = len(items)
def gen_combination(i, start_value):
if i > r - 1:
yield combination_store
else:
max_value = length - r + 1 + i # max possible value for the i-th value
for new_value in range(start_value, max_value):
combination_store[i] = new_value
for x in gen_combination(i + 1, new_value + 1):
yield x
for combination in gen_combination(0, 0):
yield tuple(item[i] for i in combination)
Some notes on how this algorithm works.
combination_storeis a list that stores the current combination. Initialised withNone’s.gen_combinationis the recursive function that yields the indexes of the combinations.gen_combinationtakes two argumentsiandstart_value.iis the item incombination_storethat will be incremented.start_valueis the value start from when iterating through the possible values for thei-th element ofcombination_store.For the
i-th element ofcombination_store, the fore loop iterates through the possible values of that particular item. Each iteration it recursively callsgen_combinationto generate the possible values of thei + 1-th element ofcombination_store.If i is greater than r - 1 that means a combination has been generated and so
combination_storeis yielded.
Let us test out this code.
>>> [i for i in combinations([0, 1, 2, 3, 4], 3)]
[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4], [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
>>> [i for i in combinations([0, 1, 2, 3, 4], 2)]
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
7.2. Implementation in the python documentation#
In the Python documentation (https://docs.python.org/3/library/itertools.html#itertools.combinations), they present a simplified version of their algorithm to generate combinations that does not use recursion. I have added a few extra comments to make it easier for me to understand.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
# This method generates combinations of the indices [0, 1, 2, ..., n]
indices = list(range(r))
# The first element yielded is from the indices [0, 1, 2, ..., r - 1]
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
# Check if the i-th element is at its maximum value
if indices[i] != i + n - r:
break
else:
# If all elements are at their maximum value return, since all combinations
# have been generated
return
# The i-th element is not at its maximum value so increment by 1
indices[i] += 1
for j in range(i+1, r):
# Set the elements to the right of the i-th element to their minimum
# possible value.
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
The main ideas behind the implementation are very similar to the implementation
above. To avoid recursion, they find the i-th element in the
indices list that is not at its maximum value. Than element is then
incremented by 1, and every element to the right of the i-th element is
1 above their left neighbour. Then it repeats the process.
Avoiding recursion makes the implementation much simpler and I suspect much
quicker. I especially like using reversed(range(r)) instead of
something like range(r - 1, -1, -1). The former is much easier to read.
7.3. Solving Sudoku#
Here is an algorithm for solving sudoku that is inspired by the python implementation of combinations in that it does not use recursive functions.
# main.py
import csv
class Board:
def __init__(self, board):
self.board = board
@classmethod
def from_csv(cls, path):
board = []
with open(path) as csvfile:
reader = csv.reader(csvfile, delimiter=',')
for row in reader:
board += [int(item) for item in row]
return cls(board)
def to_str(self, board):
board_str = ""
for i in range(9):
row = [str(item) for item in board[i * 9: i * 9 + 9]]
board_str += " ".join(row) + "\n"
return board_str
def get_square(self, i, board):
row_index, col_index = divmod(i, 9)
top_left_row_index = row_index // 3 * 3
top_left_col_index = col_index // 3 * 3
top_left_index = top_left_row_index * 9 + top_left_col_index
square = (
board[top_left_index:top_left_index + 3]
+ board[top_left_index + 9:top_left_index + 9 + 3]
+ board[top_left_index + 18:top_left_index + 18 + 3]
)
return square
def is_in_row(self, value, i, board):
row_index = i // 9
row = board[row_index * 9: row_index * 9 + 9]
return value in row
def is_in_col(self, value, i, board):
col_index = i % 9
col = board[col_index: 9 * 9: 9]
return value in col
def is_in_square(self, value, i, board):
square = self.get_square(i, board)
return value in square
def index_of_previous_unoccupied_cell(self, i):
if i == 0:
raise RuntimeError("There are no cells before the first cell.")
index = i - 1
while True:
if self.board[index] == 0:
return index
else:
index -= 1
def value_causes_conflict(self, value, i, solution) -> bool:
return (
self.is_in_row(value, i, solution)
or self.is_in_col(value, i, solution)
or self.is_in_square(value, i, solution)
)
def solve(self):
solution = self.board.copy()
i = 0
while True:
if i >= 81:
return solution
elif self.board[i] != 0:
i += 1
continue
for value in range(solution[i] + 1, 9 + 1):
if self.value_causes_conflict(value, i, solution) is False:
solution[i] = value
i += 1
break
else:
solution[i] = 0
i = self.index_of_previous_unoccupied_cell(i)
if __name__ == "__main__":
board = Board([
0, 0, 0, 2, 6, 0, 7, 0, 1,
6, 8, 0, 0, 7, 0, 0, 9, 0,
1, 9, 0, 0, 0, 4, 5, 0, 0,
8, 2, 0, 1, 0, 0, 0, 4, 0,
0, 0, 4, 6, 0, 2, 9, 0, 0,
0, 5, 0, 0, 0, 3, 0, 2, 8,
0, 0, 9, 3, 0, 0, 0, 7, 4,
0, 4, 0, 0, 5, 0, 0, 3, 6,
7, 0, 3, 0, 1, 8, 0, 0, 0,
])
sol = board.solve()
print(board.to_str(sol))
Running the file, we get the following.
$ python3 main.py
4 3 5 2 6 9 7 8 1
6 8 2 5 7 1 4 9 3
1 9 7 8 3 4 5 6 2
8 2 6 1 9 5 3 4 7
3 7 4 6 8 2 9 1 5
9 5 1 7 4 3 6 2 8
5 1 9 3 2 6 8 7 4
2 4 8 9 5 7 1 3 6
7 6 3 4 1 8 2 5 9