add these details to the function documentation

[MHenderson]

Appendix - Implementation Details

Room data frames

To represent a partial Room square in R, you can use a data frame with four columns: "row", "col", "first", and "second". Each row of the data frame corresponds to a cell in the Room square and indicates whether the cell is empty or filled.

Empty cells are identified by having "NA" values in both the "first" and "second" columns, while filled cells have non-"NA" values in both columns.

To create an empty partial Room square, you can use the expand_grid function from the tidyr package to create the "row" and "col" columns, and then use the mutate function from the dplyr package to add the "first" and "second" columns.

empty_room <- function(n) {
 expand_grid(row = 1:(n - 1), col = 1:(n - 1)) %>%
 mutate(first = as.numeric(NA), second = as.numeric(NA))
}

Although it may appear to be incorrect, a Room square of order $n$ actually has $n-1$ rows and $n-1$ columns.

Available symbols

In a partial Room square, for every empty cell $e$, there exists a set of available symbols that can be placed in that cell. These available symbols are the ones from the set ${0, ..., n - 1}$ that do not already appear in the same row or column as the cell $e$.

Instead of recalculating the available symbols set every time it is needed, it is more practical to maintain an up-to-date list of available symbols for each cell. This approach ensures that the available symbols for each cell are readily accessible whenever needed.

In an empty Room square, all symbols are initially available for every cell.

R <- empty_room(n) %>% mutate(avail = list(0:(n - 1)))

It is important to note that the lists in the avail object are not automatically updated. As a result, it is necessary to manually remove symbols from all lists in the same row and column whenever an empty cell is filled. This ensures that the available symbols for each cell remain accurate and up-to-date throughout the process of constructing the Room square.

Unused pairs and empty cells

Before beginning the iteration through cells or pairs of symbols, it is necessary to initialize global lists of unused pairs and empty cells. These lists can be updated during the iteration process, allowing you to determine which cells are empty and which pairs of symbols are unused at any given step of the process. By maintaining and updating these lists, you can ensure that the construction of the Room square proceeds smoothly and accurately.

Main loop structure

Suppose that $E$ is a global list of empty cells and $P$ is a global list of unused pairs.
The structure of greedy1 then looks something like this.

for(e in E) {

  # 1. calculate available symbols for e

  # iterate through unused pairs in given order
  for(p in P) {

    # 2. if empty cell e is suitable for pair p then:

      # 3. assign p to cell e
      # 4. remove e from the global list of empty cells
      # 5. remove p from the global list of pairs
      # 6. remove both elements of p from lists of symbols missing in row e[1]
      # 7. remove both elements of p from lists of symbols missing in col e[2]
      # 8. stop

  }

}

Details

1. Calculate available symbols for an empty cell $e$

Filter the Room data frame to just the row representing cell $e$, the available symbols are those in the vector in list column avail:

available <- R[R$row == e[1] & R$col == e[2], "avail"]$avail[[1]]

The reason for calculating available here instead of inside the nested loop where
it gets used is because it doesn't change until we assign something to $e$.
So if we were calculating it for every pair $p$ being test inside the nested loop then all but one of those computations would be redundant.

2. Test suitability of pair $p$ for $e$

Test if both p[1] and p[2] are found in available computed in step 1:

p[1] %in% available && p[2] %in% available

3. Assign $p$ to empty cell $e$

Use two assignments, one for each element of $p$.

Filter the Room dataframe to the row corresponding to $e$:

R[R$row == e[1] & R$col == e[2], ]

Assign the first element of p to the first column:

R[R$row == e[1] & R$col == e[2], "first"] <- p[1]

Assign the second element of p to the second column:

R[R$row == e[1] & R$col == e[2], "second"] <- p[2]

4. Remove e from the global vector of empty cells

Use the match function to find indices of elements of E matching empty cell e.
Use this vector of matching indices to construct a new vector containing all elements of E that don't match.
Replace E with this new vector:

E <- E[-match(list(e), E)]

5. Remove p from the global vector of available pairs

A very similar approach to the one taken in 4 works here as well:

P <- P[-match(list(p), P)]

6. Remove both elements of p from lists of available symbols for all cells in the current row

If there happened to exist a function remove_both(X, p) that would remove both elements of a pair p from X and further, if L were a list of vectors for which it was desired to remove both elements of p from every vector in L then

lapply(L, remove_both, p)

would do the trick.

Now

R[R$row == e[1], "avail"]$avail

is a list of vectors each of which represents available symbols for a cell in the same row as e so:

lapply(R[R$row == e[1], "avail"]$avail, remove_both, p)

removes both elements of p from every list of available symbols for cells in the same row as e.

Therefore

R[R$row == e[1], "avail"]$avail <- lapply(R[R$row == e[1], "avail"]$avail, remove_both, p)

updates the list of available symbols of cells in the same row as e with a new list of sets of available symbols from which both elements of p have been removed.

7. Remove both elements of p from lists of available symbols for all cells in the current column

This is almost the same as 6:

R[R$col == e[2], "avail"]$avail <- lapply(R[R$col == e[2], "avail"]$avail, remove_both, p)

8. Stop

if you don't remember to break from the loop at this point then you will continue to inspect candidate pairs even after having found a suitable one.

greedy2

Having implemented greedy1 there is almost nothing left to do to implement greedy2.
Simply change the nesting of the loops.
Now at the top level iterate over P instead of E while at the inner level iterate of E instead of P.

for(p in P) {

  for(e in E) { }

}

[MHenderson]

Move to the Wallis project.