Young Tableaus

A Young tableau is a graphical representation of integer partitions used in combinatorics and representation theory. It consists of a grid with left-justified rows of decreasing length.

Some key properties:

Each row has unique & sorted entries
Entries increase from top to bottom in each column

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int[][] youngTableau(int[] partition) {

  int n = partition.length;
  int[][] tableau = new int[n][];

  int value = 1;
  for (int i = 0; i < n; i++) {
    tableau[i] = new int[partition[i]];
    for (int j = 0; j < partition[i]; j++) {
      tableau[i][j] = value++; 
    }
  }

  return tableau;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
vector<vector<int>> youngTableau(vector<int> partition) {

  int n = partition.size();
  vector<vector<int>> tableau(n);

  int value = 1;
  for (int i = 0; i < n; i++) {
    tableau[i].resize(partition[i]);

    for (int j = 0; j < partition[i]; j++) {
      tableau[i][j] = value++;
    }
  }

  return tableau;
} 

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def young_tableau(partition):

  tableau = []
  value = 1
  
  for row_size in partition:
    row = []
    for _ in range(row_size):
      row.append(value)
      value += 1
    tableau.append(row)

  return tableau

Young tableaus elegantly model integer partitions and combinatorial objects. Useful in representation theory.

A Young Tableau is a 2D array with dimensions m x n, where the entries are integers, and the following properties hold:

Each row is sorted from left to right in ascending order.
Each column is sorted from top to bottom in ascending order.

Young Tableaus are particularly useful for tasks like priority queue operations and searching. The key takeaway is that they offer a convenient and efficient way to maintain a sorted 2D structure.

Creating a 4x4 Young Tableau containing the elements 16, 3, 2, 4, 8, 5, 14, and 12 involves inserting these elements while maintaining the tableau’s properties. After inserting these elements in any order and rearranging the tableau, one valid configuration might be:

2   3   5   8
4  12  14  ∞
16  ∞  ∞  ∞
∞  ∞  ∞  ∞

Here, “∞” denotes an empty spot in the tableau, often represented by infinity since the tableau should hold the minimum possible value at the top-left corner and “∞” will always be greater than any integer.

Note that Young Tableaus can have multiple correct configurations depending on the sequence of insertions. The essential property is that the rows and columns must be sorted in ascending order.

Java Code for Young Tableaus

In Java, we can represent a Young Tableau using a 2D array and provide methods to insert and extract minimum elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class YoungTableau {
    int[][] table;
    int m, n;

    public YoungTableau(int m, int n) {
        this.m = m;
        this.n = n;
        this.table = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                table[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    public void insert(int val) {
        table[m - 1][n - 1] = val;
        // Code for heapify-up operation
    }

    public int extractMin() {
        int minVal = table[0][0];
        table[0][0] = Integer.MAX_VALUE;
        // Code for heapify-down operation
        return minVal;
    }
}

insert(int val) adds a new value while maintaining the Young Tableau properties.
extractMin() returns and removes the smallest value in the tableau.

C++ Code for Young Tableaus

In C++, you can achieve the same functionality using a 2D vector.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <climits>
using namespace std;

class YoungTableau {
private:
    vector<vector<int>> table;
    int m, n;

public:
    YoungTableau(int m, int n): m(m), n(n), table(m, vector<int>(n, INT_MAX)) {}

    void insert(int val) {
        table[m - 1][n - 1] = val;
        // Code for heapify-up operation
    }

    int extractMin() {
        int minVal = table[0][0];
        table[0][0] = INT_MAX;
        // Code for heapify-down operation
        return minVal;
    }
};

insert(int val) handles new element insertion.
extractMin() retrieves and removes the minimum value.

Python Code for Young Tableaus

Python’s list comprehensions and native 2D lists make the implementation straightforward.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class YoungTableau:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.table = [[float('inf') for _ in range(n)] for _ in range(m)]

    def insert(self, val):
        self.table[-1][-1] = val
        # Code for heapify-up operation

    def extract_min(self):
        min_val = self.table[0][0]
        self.table[0][0] = float('inf')
        # Code for heapify-down operation
        return min_val

insert(self, val) is for inserting a new value.
extract_min() retrieves the smallest value and removes it from the tableau.

In these implementations, the methods insert and extractMin (or extract_min in Python) are crucial. These methods maintain the properties of the Young Tableau while performing operations. The actual heapify-up and heapify-down logic has been omitted for brevity but is essential to fully implement these methods.