14.1 Permutation and Operator Sequence

In solving the 24 Game, the goal is to perform three operations on four integers to achieve the target result. Without prior knowledge, one effective method is exhaustive search. Let’s use the example \(1, 5, 5, 5\) for this demonstration.

14.1.1 Breaking Down a Solution

Revisiting the example solution from the chapter introduction:

\[ 5 \times (5 - 1 / 5) = 24 \]

We can break this equation into the following three steps:

  1. \(1 / 5 = 0.2\)
  2. \(5 - 0.2 = 4.8\)
  3. \(5 \times 4.8 = 24\)

Key observations: 1. Each step involves two numbers and one operator. For example, the first step uses \(1\) and \(5\) with the / operator. 2. Numbers in the first step come directly from the input. 3. In subsequent steps, one number is the result from the previous step, and the other comes from the input.

14.1.2 Getting All Permutations

The three steps imply a specific order of the original four numbers. In this case, we have 1, 5, 5, 5. In our exhaustive search, we need to enumerate all possible permutations of the original four number, which at most is \(4! = 24\). We can find all the possible permutations using the permutations() function in the gtools package. We also apply the unique() function to eliminate duplicate permutations.

library(gtools)
nums <- c(1, 5, 5, 5)
n_nums <- length(nums)
nums_perm <- unique(permutations(n_nums, n_nums, nums, set = FALSE))
nums_perm
#>      [,1] [,2] [,3] [,4]
#> [1,]    1    5    5    5
#> [2,]    5    1    5    5
#> [3,]    5    5    1    5
#> [4,]    5    5    5    1

nums_perm is now a matrix where each row represents one unique permutation.

14.1.3 Getting All Operators

With the nums_perm in hand, we have a specific ordering of the original numbers that we will use in the calculation. Let’s take a look at the first row, (1, 5, 5, 5). The first step will then involve the numbers 1 and 5. How many possible operations are there between them? At first, maybe you think there are four \(1 + 5\), \(1 - 5\), \(1 \times 5\), and \(1 / 5\). Actually, the - and / operators are not symmetric. And we will get a different result when we switch the order, unless the two numbers are the same. As a summary, for numbers x and y, we have the following six possible operations.

Operator Example Value
x + y 1 + 5 6.0
x - y 1 - 5 -4.0
y - x 5 - 1 4.0
x * y 1 * 5 5.0
x / y 1 / 5 0.2
y / x 5 / 1 5.0

Now, we need to make this process automatic. Let’s write the following function cal() which takes arguments x, y, and op (a value from 1 to 6).

cal <- function(x, y, op) {
    switch(op, x + y, x - y, x * y, x/y, y - x, y/x)
}

To output the intermediate steps, it is useful to write a print function. The following function print_op(x, y, z, op) will generate a string that represent the operation op between x and y generates z.

print_op <- function(x, y, z, op) {
    switch(op, paste(x, "+", y, "=", z), paste(x, "-", y, "=", z), paste(x, "*",
        y, "=", z), paste(x, "/", y, "=", z), paste(y, "-", x, "=", z), paste(y,
        "/", x, "=", z))
}

Since we have three steps and each step has 6 possible operators, there are in total \(6^3 = 216\) possible combinations of the operator sequence. Let’s get all the combinations as below.

n_ops <- 6
op_mat <- permutations(n_ops, n_nums - 1, repeats.allowed = TRUE)
head(op_mat, 10)
#>       [,1] [,2] [,3]
#>  [1,]    1    1    1
#>  [2,]    1    1    2
#>  [3,]    1    1    3
#>  [4,]    1    1    4
#>  [5,]    1    1    5
#>  [6,]    1    1    6
#>  [7,]    1    2    1
#>  [8,]    1    2    2
#>  [9,]    1    2    3
#> [10,]    1    2    4

Let’s look at some possible row for the example (1, 5, 5, 5).

Operator_Seq Step1 Step2 Step3 Value
1, 2, 3 1 + 5 (1 + 5) - 5 ((1 + 5) - 5)*2 2
5, 3, 4 1 / 5 5 - 1 / 5 (5 - 1 / 5)*5 24
6, 2, 1 5 / 1 5/1 - 5 5/1 - 5 + 5 5

Out of all possible operator sequence, it turns out some of them are redundant when we also consider all permutations of the numbers. The most obvious ones are the operator sequence that starts with 5 or 6. To see this, note that cal(x, y, 5) and cal(y, x, 2) both equal y - x, and cal(x, y, 6) and cal(y, x, 4) both equal to y/x. Therefore, we can safely remove all operator sequences that start with 5 or 6.

op_mat <- op_mat[op_mat[, 1] <= 4, ]

There are in total 144 possible operator sequences for each number sequence.