======================== 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 :math:`[i_0, i_1, \dots, i_{n-1}]`. Write out each permutation of pairs (with replacement) as a matrix. .. math:: \begin{matrix} (i_0, i_0) & (i_0, i_1) & \dots & (i_0, i_{n-1}) \\ (i_1, i_0) & (i_1, i_1) & \dots & (i_1, i_{n-1}) \\ \vdots & \vdots & & \vdots \\ (i_{n-1}, i_0) & (i_{n-1}, i_1) & \dots & (i_{n-1}, i_{n-1}) \\ \end{matrix} The matrix contains all possible permutations (with replacement). The matrix is symmetric meaning for each pair :math:`(i_a, i_b)` below the diagonal, the pair :math:`(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 :math:`i = [i_0, i_1, \dots, i_{n-1}]`. Suppose we generate all the permutations that start with :math:`i_a` for :math:`a=0, 1, \dots, b - 1` where :math:`b \leq n - 1`. Then, for the list of permutations that start with :math:`i_b`, then :math:`(i_j, i_b)` has already been generated if :math:`j < b`. Let us write our function to generate combinations. .. code:: >>> 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 :math:`r=3`. Let us try extending the rule we defined above and used it for the case where :math:`r=3`. .. code:: >>> 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 :code:`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 :code:`r=3` and potentially any value :code:`r`. ----------------------------------- 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 :code:`r=3` creating a matrix is not as simple. For the :code:`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 :code:`r` increases? What can we gain from the matrix representation for :code:`r=2` that could be applied to :code:`r=3`? First recall the matrix representation for :code:`r=2`. .. math:: \begin{matrix} (i_0, i_0) & (i_0, i_1) & \dots & (i_0, i_{n-1}) \\ (i_1, i_0) & (i_1, i_1) & \dots & (i_1, i_{n-1}) \\ \vdots & \vdots & & \vdots \\ (i_{n-1}, i_0) & (i_{n-1}, i_1) & \dots & (i_{n-1}, i_{n-1}) \\ \end{matrix} 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 :math:`(i_a, i_b)` where :math:`b < a`. Extending this to the length 3 case, we can say the set of length 3 combinations is the set of permutations :math:`(i_a, i_b, i_c)` where :math:`a < b < c`. We can prove this by contradiction. Suppose we have the set of all combinations, :math:`(i_a, i_b, i_c)`, where :math:`i_a < i_b < i_c`. Suppose there is another combination :math:`(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, :math:`(i_a, i_b, i_c)`, such that :math:`i_a < i_b < i_c`. Keeping that in mind, let us generate the length three combinations of :math:`[1, 2, 3, 4]`. .. code:: [1, 2, 3] [1, 2, 4] [1, 3, 4] [2, 3, 4] The above combinations all satisfy :math:`i_a < i_b < i_c`. The combinations were generated by starting with the *minimum* combination, :code:`[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. .. code:: 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. * :code:`combination_store` is a list that stores the current combination. Initialised with :code:`None`'s. * :code:`gen_combination` is the recursive function that yields the indexes of the combinations. * :code:`gen_combination` takes two arguments :code:`i` and :code:`start_value`. :code:`i` is the item in :code:`combination_store` that will be incremented. :code:`start_value` is the value start from when iterating through the possible values for the :code:`i`-th element of :code:`combination_store`. * For the :code:`i`-th element of :code:`combination_store`, the fore loop iterates through the possible values of that particular item. Each iteration it recursively calls :code:`gen_combination` to generate the possible values of the :code:`i + 1`-th element of :code:`combination_store`. * If `i` is greater than `r - 1` that means a combination has been generated and so :code:`combination_store` is yielded. Let us test out this code. .. 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]] ------------------------------------------ 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. .. code:: 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 :code:`i`-th element in the :code:`indices` list that is not at its maximum value. Than element is then incremented by 1, and every element to the right of the :code:`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 :code:`reversed(range(r))` instead of something like :code:`range(r - 1, -1, -1)`. The former is much easier to read. -------------- 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. .. code:: # 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. .. code:: $ 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