a m * n young tableau is an m*n matrix such that the entries of each row are in sorted order from left to right and entries of each column are in sorted order from top to bottom
some of the entries in the young tableau may be empty or non existent represented by infinity.
maximum number of elements r <= m * n.
There are two things to consider here..
1.If young[0,0] = non existent or infinity.since rows and columns must contain elements in ascending order and infinity is the largest element out there and it is already present at the first position we can't have any element in the table anymore.so the table must be empty.
2. similarly if young[m-1,n-1] < infinity,the table is full and we can't insert element any more.
The minimum element in young tableau is stored at young[0,0] and maximum element is stored at young[m-1,n-1]
1.searching
suppose you want to search a number in young tableau.start with the lowest left corner i.e element at a[m-1][0] position and move forward if element > a[m-1][0] or upward if element < a[m-1][0].
based on the property that any element a[i][j],a[i][j+1] > a[i][j] and a[i-1][j]< a[i][j]
[cpp]
search_young(Y,3,3,3,0,22);
void search_young (int Y[][10],int m,int n,int i,int j,int element){
if (i<0 || j > n)
printf("no such element is there");
else if (Y[i][j]==element)
printf("element is present");
else if (Y[i][j]<element)
search_young(Y,m,n,i-1,j,element);
else
search_young(Y,m,n,i,j+1,element);
}
[/cpp]
time complexity
In best case the element is present at the lower left corner
In worst case (when searched element is present) and the algorithm will take O(m+n) time
It will check m+n elements at max.
sorting
we can also sort the young tableau but the method is very expensive in terms of time complexity.
[cpp]
void sort_tableau(){
int temp[2*m];
for (i=0;i<m-1;++i){
for(p=0,q=0;p<n && q<n;)
if (a[i][p]<a[i+1][q])
temp[c++]=a[i][p++];
else
temp[c++]=a[i+1][q++];
if (q<n)
for(int j=q;j<n;++j)
temp[c++]=a[i+1][j];
else
for(int j=p;j<n;++j)
temp[c++]=a[i][j];
int c=0;
for(int l=i;l<=i+1;++l)
for(int k=0;k<n;++k)
a[l][k]=temp[c++];
}
}
[/cpp]
Inserting
suppose you have a young tableau in which there exist some empty positions like this one
after inserting the element ,you have to set that element in the correct position so that the matrix will again satisfy young tableau property
[cpp]
void insert_young(int Y[][],int m,int n,int i,int j,int element){
int d1,int d2;
if (Y[i][j]!=INT_MAX || i>=m || j>=n )
return;
else
a[i][j]=element;
if (j-1<0 || a[i][j-1]<a[i][j])
d1=-1;
else d1=a[i][j-1]-a[i][j];
if (i-1<0 || a[i-1][j]<a[i][j])
d2=-1;
else
d2=a[i-1][j]-a[i][j];
if (d1 <0 and d2 < 0)
return;
else if (d1>d2)
{
a[i][j]=a[i][j-1];
a[i][j-1]=INT_MAX;
j=j-1;
}
else{
a[i][j]=a[i-1][j];
a[i-1][j]=INT_MAX;
i=i-1;
}
insert(Y,m,n,i,j,element);
}
[/cpp]
best case will occur when you have empty young tableau and you are inserting the element at first position i.e at Y[0][0].
Time complexity Omega(1)
worst case will occur when you are inserting the element at Y[m-1][n-1] plus the inserted element is the smallest .In this case
Time complexity O(m+n)
Extract minimum
In any young tableau the minimum element is present at the Y[0,0] position which we can extract easily,Our main problem lies in arranging its remaining elements so that it can again satisfy young tableau property.
[cpp]
int extract_minimum_young(int Y[][],int m,int n,int i,int j){
int min = Y[i][j];
while(i+1<m || j+1 < n){
if (j+1 >=n || a[i+1][j] < a[i][j+1])
a[i][j]=a[i+1][j];
a[i+1][j]=INT_MAX;
i=i+1;
else {
a[i][j]=a[i][j+1];
a[i][j+1]=INT_MAX;
j=j+1;
}
}
}
return min;
}
[/cpp]
0 comments: