Young tableau

Definition

已知一个2维矩阵，其中的元素每一行从左至右依次增加，每一列从上到下依次增加。即对于矩阵Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我们也称这样的矩阵为杨氏矩阵。

Insert

因为每个元素的下面一个元素和右面一个元素都会比当前元素大，所以右下角的元素是最大的一个元素。所以我们将元素放到矩阵的右下角，然后再来调整元素的位置。我们将这个元素与它上面的元素和左面的元素进行比较，将最大的那个元素与这个元素进行交换，如果这个元素就是最大的话，则已经插入正确的位置。若上面和左面的两个元素相等且大于这个元素，则我们可以交换哪一个都可以。

Delete

我们要把矩阵中指定的一个元素去掉，那么我们需要调整它右面和下面的元素来符合杨氏矩阵的特性。所以我们不妨将要删除的元素置为NAN。我们将这个元素与他右面和下面的元素中最小的那个进行交换(类似insert操作)

Find

我们从右上角开始来查找，目的元素比当前元素大则向下查，比当前元素小则向左查。这样们可以在2*n的次数内找到想要的元素。

Modify

我们将这个重新赋值的元素和它四周的元素进行比较，通过交换调整位置来满足杨氏矩阵的特性。

#-*-coding:utf-8-*-
from numpy import *

def insert(m, value, i, j):
    m[i][j] = value
    largesti = i
    largestj = j

    if i-1>=0 and (isnan(m[i-1][j]) or m[i-1][j] > m[i][j]):
        largesti = i-1
        largestj = j
    if j-1>=0 and (isnan(m[i][j-1]) or m[i][j-1] > m[largesti][largestj]):
        largesti = i
        largestj = j - 1
    if i!=largesti or j!=largestj:
        temp = m[i][j]
        m[i][j] = m[largesti][largestj]
        m[largesti][largestj] = m[i][j]
        insert(m,value,largesti,largestj)

def delete(m, i, j):
    m[i][j] = NAN
    mini = i
    minj = j
    if i+1<m.shape[0]:
        mini = i+1
        minj = j
    if j+1<m.shape[1] and (isnan(m[mini][minj]) or m[i][j+1] < m[mini][minj]):
        mini = i
        minj = j+1

    if mini!=i or minj!=j:
        temp = m[i][j]
        m[i][j] = m[mini][minj]
        m[mini][minj] = temp
        delete(m, mini, minj)

def find(m,value):
    i = 0
    j = m.shape[1] - 1
    while i<m.shape[0] and j >=0:
        if isnan(m[i][j]) or m[i][j] > value:
            j = j -1
        elif isnan(value) or m[i][j] < value:
            i = i+ 1
        else:
            return True
    return False

def modify(m, i, j, value):
    m[i][j] = value
    nexti = i
    nextj = j
    if i-1>=0 and m[i-1][j] > m[i][j]:
        nexti = i-1
        nextj = j
    if j-1>=0 and m[i][j-1] > m[nexti][nextj]:
        nexti = i
        nextj = j-1

    if i+1<m.shape[0] and m[i][j] > m[i+1][j]:
        nexti = i+1
        nextj = j
    if j+1<m.shape[1] and( isnan(m[nexti][nextj]) or m[i][j+1] < m[nexti][nextj]):
        nexti = i
        nextj = j+1

    if nexti!=i or nextj!=j:
        temp = m[i][j]
        m[i][j] = m[nexti][nextj]
        m[nexti][nextj] = temp
        modify(m, nexti, nextj, value)

if __name__ == '__main__':
    m = array([[2,4,6,NAN],[3,7,10,NAN],[5,12,NAN,NAN],[8,NAN,NAN,NAN]])
    h,v = m.shape
    print 'matrix'
    print m
    print '-'*24
    print 'after insert 7'
    insert(m,7,h-1,v-1)
    print m
    print '-'*24
    print 'after delete m[0][0]'
    delete(m,0,0)
    print m
    print '-'*24
    print 'if 12 in the matrix'
    print find(m,12)
    print '-'*24
    print 'after update m[1][1] to 1'
    modify(m, 1, 1,1)
    print m

脚本输出

matrix
[[  2.   4.   6.  nan]
 [  3.   7.  10.  nan]
 [  5.  12.  nan  nan]
 [  8.  nan  nan  nan]]
------------------------
after insert 7
[[  2.   4.   6.  nan]
 [  3.   7.  10.  nan]
 [  5.   7.  nan  nan]
 [  8.  12.  nan  nan]]
------------------------
after delete m[0][0]
[[  3.   4.   6.  nan]
 [  5.   7.  10.  nan]
 [  7.  12.  nan  nan]
 [  8.  nan  nan  nan]]
------------------------
if 12 in the matrix
True
------------------------
after update m[1][1] to 1
[[  1.   4.   6.  nan]
 [  3.   5.  10.  nan]
 [  7.  12.  nan  nan]
 [  8.  nan  nan  nan]]