Monday, June 6, 2016

Print sorted from a matrix which is rowwise and columwise sorted
This is an online solution though I don't agree with it
Such a matrix is called Young's Tableau
int extractMin(int m[,], int N)
{
    int ret = m[0,0];
    m[0,0] = INT_MAX;
    youngify(m, N, 0, 0);
    return ret;
}
void youngify(int[,] m, int N, int i, int j)
{
    int down  = (i+1 < N)? m[i+1,j]: INT_MAX;
    int right = (j+1 < N)? m[i,j+1]: INT_MAX;

    if (down==INT_MAX && right==INT_MAX)
        return;

    if (down < right)
    {
        m[i,j] = down;
        m[i+1,j] = INT_MAX;
        youngify(m, i+1, j);
    }
    else
    {
        m[i,j] = right;
        m[i,j+1] = INT_MAX;
        youngify(m, i, j+1);
    }
}
The example that seems to break this is
1   2    9
3   4   11
10 12 13

The correct approach should be :
void youngify(int[,] m, int N, int i, int j)
{
int si = i;
int sj = j;
if (i+1<=N and Y[i,j] > Y[i+1,J]){
si = i + 1;
sj = j;
}
if (j+1<=N and Y[i,j] > Y[i,j+1]{
si = i;
sj = j + 1;
}
if (si != i && sj != j){
Swap(m[si,sj], m[i,j]);
youngify(Y, si, sj);
}

}


Get zero sum elements from a list of positive and negative integers:
void GetZeroSum(List<int> A, int sum, ref List<int> candidate, int start, int level)
{
for (int i = start; i < A.Length; i++)
{
    for (int k = 0; k < 3; k++){
      candidate[level+k] = A[i];
      if (candidate.Sum() == sum)
          print (candidate.toString());
      if (level+k < 3)
         GetZeroSum(A, sum, ref candidate, start+1, level+k+1);
      candidate[level+k] = 0;
    }
}
}
// Trial runs from this approach
[-3, 6]
Sum 0
Candidate on different iterations:
-3
-3 6
-3 6 6 
-3 -3 6  print
-3 -3 -3
6 6
6 6 6

GetZeroSum(List<int> A, int sum, ref List<int> candidate)
{
if (candidate.Sum() == sum) return True;
if (candidate.Count() > 3) return False;
if (A.Count() == 0) return False;
if (A[0] == 0 && sum == 0) return True;
for (int i = 1; i <= 3; i++)
{
    candidate.Add(A[0]);
    var localsum = candidate.sum();
    if (localsum + A.sum() > sum) break; // or add other conditions to terminate early
    if (GetZeroSum(A.Remove(A[0]), sum, ref candidate) ||
        GetZeroSum(A.Remove(A[0]), sum-localsum, ref candidate))
        return True;
}
return False;
}

No comments:

Post a Comment