dynamic programming and maximum length of a sequence of rectangles that fit into each other

Question

Given a set of n rectangles as {(L1, W1), (L2, W2), …….., (Ln, Wn)}, Li and Wi indicate the length and width of rectangle i, respectively. We say that rectangle i fits in rectangle j if Li< Lj and Wi< Wj.

I need help designing a O( nˆ2 ) dynamic programming algorithm that will find the maximum length of a sequence of rectangles that fit into each other.

I made an attempt, but it is not working in some cases, which are as follows:

LR(i, j)= { 2+ LR(i-1, j-1)  if (Li< Lj and Wi< Wj) or (Lj< Li and Wj< Wi)

             Max ( LR(i+1, j), LR (I, j-1)  otherwise   }

Could you please help me improve my solution or find better one?

Answer 1

With DP you can do it as follows:

• Sort the rectangles by decreasing width, and sort ties by decreasing height
• For each index in the array of rectangles, determine the best solution if that rectangle is the first one taken (the outermost containing rectangle), and store it for later lookoup
• Use recursion to determine the greatest number of rectangles that can fit when the current rectangle is taken (1) or not taken (2). Take the greatest result of both.

Here is an implementation in JavaScript which you can run here:

function maxNumberOfFittingRectangles(rectangles) {
     // Storage of optimal, intermediate results (DP principle), 
     //    keyed by the index of the first rectangle taken
    let memo = new Map;

    // Take a copy of rectangles, and sort it in order of decreasing width, 
    //    and if there are ties: by decreasing height
    rectangles = [...rectangles].sort( (a, b) => (b.width - a.width) 
                                              || (b.height - a.height) );
    
    function recurse(maxHeight, startIndex) {
        for (let i = startIndex; i < rectangles.length; i++) {
            if (rectangles[i].height <= maxHeight ) { // Can fit
                // Try a solution that includes rectangles[i]
                // - Only recurse when we did not do this before
                if (!(memo.has(i))) memo.set(i, recurse(rectangles[i].height, i+1)+1);
                // Also try a solution that excludes rectangles[i], and 
                // return best of both possibilities:
                return Math.max(memo.get(i), recurse(maxHeight, i+1));
            }
        }
        return 0; // recursion's base case
    }
    
    let result = recurse(Infinity, 0);
    // Display some information for understanding the solution:
    for (let i = 0; i < rectangles.length; i++) {
        console.log(JSON.stringify(rectangles[i]), 
                    'if taken as first: solution = ', memo.get(i));
    }
    
    return result;
}

// Sample data
let rectangles = [
    { width: 10, height:  8 },
    { width:  6, height: 12 },
    { width:  4, height:  9 },
    { width:  9, height:  9 },
    { width:  2, height:  9 },
    { width: 11, height:  4 },
    { width:  9, height:  5 },
    { width:  8, height: 11 },
    { width:  6, height:  6 },
    { width:  5, height:  8 },
    { width:  2, height:  7 },
    { width:  3, height:  5 },
    { width: 12, height:  7 },
];

let result = maxNumberOfFittingRectangles(rectangles);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Get the actual rectangles

The above will give you the maximised count, but not which rectangles you would need to choose to achieve that count. You can change the algorithm slightly, by building a linked list, where you keep not only the maximised count of rectangles that can be picked after a given rectangle (in the sorted order), but also which one would be the next to pick.

Here it is:

function maxNumberOfFittingRectangles(rectangles) {
    let memo = new Map;
    rectangles = [...rectangles].sort( (a, b) => (b.width - a.width) 
                                              || (b.height - a.height) );
    
    function recurse(maxHeight, startIndex) {
        for (let i = startIndex; i < rectangles.length; i++) {
            if (rectangles[i].height <= maxHeight ) { // Can fit
                if (!(memo.has(i))) memo.set(i, recurse(rectangles[i].height, i+1));
                let result = recurse(maxHeight, i+1);
                if (memo.get(i).size < result.size) return result;
                return { next: i, size: memo.get(i).size + 1 };
            }
        }
        return { next: null, size: 0 }; // recursion's base case
    }
    
    let result = recurse(Infinity, 0);
    // Turn linked list into array of rectangles:
    let arr = [];
    while (result.next !== null) {
        arr.push(rectangles[result.next]);
        result = memo.get(result.next);
    }
    return arr;
}

// Sample data
let rectangles = [
    { width: 10, height:  8 },
    { width:  6, height: 12 },
    { width:  4, height:  9 },
    { width:  9, height:  9 },
    { width:  2, height:  9 },
    { width: 11, height:  4 },
    { width:  9, height:  5 },
    { width:  8, height: 11 },
    { width:  6, height:  6 },
    { width:  5, height:  8 },
    { width:  2, height:  7 },
    { width:  3, height:  5 },
    { width: 12, height:  7 },
];

let result = maxNumberOfFittingRectangles(rectangles);

console.log(JSON.stringify(result));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

I'm not sure about the DP algorithm here but here's what can be done in O(n^2):

• For your set of rectangles create a Directed Acyclic Graph where vertices correspond to rectangles and an edge goes from A to B if (corresponding) rectangle B fits into A.

• Find the longest path in the graph you've constructed - http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/Docs/longest-path-in-dag.pdf That path will correspond to the longest sequence you're searching for.

Answer 3

If you really want to design a DP solution, here is one you can consider: we can apply the fact that a rectangle with smaller area can't fit into the one with larger area:

1. Sort the array of rectangles based on their areas (L x W) in descending order (rectangle with the largest area is at index 0).

2. Starting with the first largest rectangle (let's call head rectangle), we then find the lengths of all sequences this head rectangle has, and get the max length from those lengths (keep reading)

   a. The head rectangle may have many sequences. To find the sequences, take the smaller rectangles that can fit into head rectangle, call each of them next_head and recursively 1) take each second rectangle next_head as a head 2) find all sub-sequences this next_head has. As the array is already sorted, we just need to check the rectangles after next_head.

   b. The base case: for the last item of one sequence, it will have no subsequence. Then, return 1 because the length of this subsequence is 1 (the head/last item itself counted as 1). For other items not the last in one sequence, they may have more than one sub-sequences. Compare the lengths those sub-sequences return and take the largest value, call it max_length. Then, return max_length + 1 (max_length is its sub-sequence's maximum length; +1 is the head itself)

3. Now do Step 2 for other rectangles, getting the maximum length each rectangle has. You may want to skip the rectangles that are already counted in another sequence.

Java code below:

class Rectangle {
  double L;
  double W;
  double area;
}

public int maxSequences(Rectangle[] rects) {
  // Sort the array based on area. You can do this by yourself
  sortBasedOnArea(rects);

  int max = 0;

  // Find the maximum length of a sequence of each rectangle: 
  // starting from biggest rectangle to smallest rectangle
  // You can improve this for loop by skipping the rectangles that are already counted in sequence before.

  for (int i = 0; i < rects.length; i++) {

    // For rectangle at index i,
    // temp_max is the maximum length of sequence 
    // the rectangle can make with other smaller rectangles
    // Simply put, temp_max is the max number of smaller rectangles that can fit into rect[i]
    int temp_max = maxSequencesHelper(rects, i);

    if (temp_max > max)
        max = temp_max;
  }

  return max;
}

public int maxSequencesHelper(Rectangle[] rects, int current_head) {
  // Head rectangle
  Rectangle head = rects[current_head];

  // Max of sub-sequence rectangles, excluding the head
  int max = 0;

  // Loop through smaller rectangles with area < head
  for (int i = current_head + 1; i < rects.length; i++) {
    Rectangle next_rect = rects[i];

    if (isFit(head, next_rect)) {
      // If this rectangle can fit into our head,
      // Recursively call this function with this rectangle as the head

      int next_head_index = i; // This just improves code readability
      int temp_max = maxSequencesHelper(rects, next_head_index);
      if (temp_max > max)
        max = temp_max;
    }
  }

  if (max == 0)
    // max = 0 when the if (isFit) in the for loop never runs
    // Therefore, this rectangle is the last item of this sequence
    return 1;
  else
    return max + 1;
}

public boolean isFit(Rectangle big, Rectangle small) {
  return small.L < big.L && small.W < big.W;
}

Please note that DP may not be the best method, and again my code above isn't the most efficient! One thing you can improve that DP method is to store the solution max length of each sequence of rectangles, but the basic idea of DP for this problem is captured above.

If there is anything unclear, feel free to add comments below.

Hope this helps!