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:
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;
}
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 6
{
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