A backtracking Solution to the Pattern132 Problem

mgcadmin 01-01-2023

Pattern132 is an interesting problem I've seen floating around on various message boards. It is a constraint satisfaction problem that I've seen all manner of solutions for ranging from dynamic programming, to straight brute force iteration. When I first scoped the problem I immediately thought it was the kind of problem that would be fun to solve with backtracking, and so I present a backtracking solution to the Pattern132 problem.

The Problem

As already mentioned, the Pattern 132 problem is a constraint satisfaction problem. Given a list of numbers where the values i, j, and k are the index of items in the list. Find if there is a sequence of values in the provided list that meet the following criteria:

i < j < k AND list[i] < list[k] < list[j]

For example, the input array, {1, 3, 4, 2} matches Pattern132 with the given i, j, k of (0, 1, 3) and (0, 2, 3).

Finding a solution with backtracking

Backtracking algorithms all follow a basic pattern, which i describe below in pseudocode:

bool backtracking(input list, index i, index j, index k) {
      if (the input parameters match a solution) {
           display solution
           return true;
      }
      if (the next input permutation is promising) {
         backtracking(input list, new index i, new index j, new index k)
     }
}

Starting from our framework we know we are going to need a few things to implement our backtracking algorithm:

• A test to determine if our current configuration of inputs is a solution
• A test to determine if the next input permutation looks promising.
•  

It is this promising function that allows us to trim the search space, and differentiates this method from being a brute force enumeration, this in combination with the recursive nature of our depth first search through the search space is what makes backtracking algorithms efficient.

The test to check for a solution is simple:

bool isSolution(input list, int i, int j, int k) {
      if (i < j < k && list[i] < list[k] < list[j]) {
           return true;
      }
      return false;
}

So now we need our promising function. To do this, we need to know how we are going to implement the permutation, to know if its worth looking at. As our backtracking function stands right now, we have the input list, and index i, index j, and index k of the list. To implement backtracking we will use the following calls:

backtracking(input list, i + 1, j, k)
backtracking(input list, i, j + 1, k) 
backtracking(input list, i, j, k + 1) 

So our promising function should check: does our input permutation satisfy the first condition of our solution, that is, i < j < k? if so, we can proceed to check if it has a solution. This means the above function calls should be wrapped like this:

bool isPromising(int i, int j, int k) {
   return (i < j) && (j < k);
}

 
if (isPromising(i+1, j, k)) backtracking(input list, i + 1, j, k)
if (isPromising(i, j+1, k)) backtracking(input list, i, j + 1, k) 
if (isPromising(i, j, k+1)) backtracking(input list, i, j, k + 1)   

Putting it all together

Now that we have our plan of attack, its a simple matter of putting it all together into a working algorithm:

 public class Pattern132 {

    private static boolean isValidPattern(int[] a, int i, int j, int k) {
        if (isPromising(i, j, k)) {
                if (a[i] < a[k] && a[k] < a[j]) {
                    return true;
                }
        }
        return false;
    }

    public static boolean isPromising(int i, int j, int k) {
            return (i < j  && j < k);
    }

    public static boolean backtracking132(int[] a, int i, int j, int k) {
        if (isValidPattern(a, i, j, k)) {
            System.out.println("[" + i + ", " + j + ", " + k + "]");
            System.out.println("(" + a[i] + ", " + a[j] + ", " + a[k] + ")");
            return true;
        }
        if (i+1 < a.length && isPromising(i+1, j, k)) backtracking132(a, i+1, j, k);
        if (j+1 < a.length && isPromising(i, j+1, k)) backtracking132(a, i, j+1, k);
        if (k+1 < a.length && isPromising(i, j, k+1)) backtracking132(a, i, j, k+1);

        //else
        return false;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 3, 4, 2};
        backtracking132(a, 0, 1, 2);
    }
}  

You'll notice the initial call to the backtracking function has the indexes 0, 1, 2 to start. We COULD use 0, 0, 0 as starting indices but we already know it would fail our promising function, so we might as well start with the first possible combination of indices that could satisfy i < j < k: 0, 1, 2.

 

 

---