[algogeeks] Re: Matrix Searching
For a large list of words, At each location, look for the character before/after that character in the word on opposite sides of the initial location, and continue from there Is it like: frequency count of 'a' is smallest 'a' is in 2 words available and alpha shall we check for 'v' near 'a'; if found then look for the complete word OR look for 'v' and 'i' on both sides of 'a'; if found then search for remaining characters in both directions OR look for 'l' and 'b' on both sides of 'a'; if found then search for remaining characters in both directions OR look for 'l' 'a'; if found then search for remaining characters in that direction OR look for 'h' 'a'; if found then search for remaining characters in that direction Is this what we should be doing? On Saturday, 15 September 2012 01:43:14 UTC+5:30, Don wrote: I had to do something like this with a large list of words to search for. If you're just looking for one word, look for the first letter, and when you find it, look at adjacent locations for the second letter. If found, continue in that direction matching letters until you either match the whole word or don't. But for a big list of words to search for, it was faster to do something like this: Build a frequency count for each character, along with a list of ordered pairs indicating where that character is located. Then, to look for a word, find the character with the smallest frequency count and step through the list for that character. At each location, look for the character before/after that character in the word on opposite sides of the initial location, and continue from there. Don On Sep 14, 2:47 pm, Arun Kindra reserve4placem...@gmail.com wrote: *You have given any n*n matrix in which characters are stored and you have to search that a given word is present or not.(words can be horizontally, vertically, diagonally)* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/tKJcCEYJsjAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Matrix Searching
I had to do something like this with a large list of words to search for. If you're just looking for one word, look for the first letter, and when you find it, look at adjacent locations for the second letter. If found, continue in that direction matching letters until you either match the whole word or don't. But for a big list of words to search for, it was faster to do something like this: Build a frequency count for each character, along with a list of ordered pairs indicating where that character is located. Then, to look for a word, find the character with the smallest frequency count and step through the list for that character. At each location, look for the character before/after that character in the word on opposite sides of the initial location, and continue from there. Don On Sep 14, 2:47 pm, Arun Kindra reserve4placem...@gmail.com wrote: *You have given any n*n matrix in which characters are stored and you have to search that a given word is present or not.(words can be horizontally, vertically, diagonally)* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix
hii I think this code will work
#includestdio.h
#includestring.h
void largestsum(int a[],int n)
{
int s=0,e=0,ls=0,max=0,j,i,sum=0;
for(i=0;in;i++)
{
sum+=a[i];
if(summax)
{
max=sum;
e=i;
s=ls;
}
if(sum0)
{
sum=0;
ls=i+1;
}
}
printf(\nlargest sum is=%d\n,max);
printf(The element which make largest sum is\t);
for(j=s;j=e;j++)
{
printf(%d\t,a[j]);
}
}
int main() {
int a[]={6,4,-5,5,2,8,-21,15,4};
int n=9;
largestsum(a,n);
return 0;
}
Thanks Regards
Sinjan
M.Tech(s/w engg)
DTU delhi
On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote:
given a matrix with +ve and -ve numbers, find the submatrix with maximum
sum??
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix
@sinjanspecial:
i think your code is for an 1 D matrix..but i have to find for a 2D matrix..
On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial sinjanspec...@gmail.comwrote:
hii I think this code will work
#includestdio.h
#includestring.h
void largestsum(int a[],int n)
{
int s=0,e=0,ls=0,max=0,j,i,sum=0;
for(i=0;in;i++)
{
sum+=a[i];
if(summax)
{
max=sum;
e=i;
s=ls;
}
if(sum0)
{
sum=0;
ls=i+1;
}
}
printf(\nlargest sum is=%d\n,max);
printf(The element which make largest sum is\t);
for(j=s;j=e;j++)
{
printf(%d\t,a[j]);
}
}
int main() {
int a[]={6,4,-5,5,2,8,-21,15,4};
int n=9;
largestsum(a,n);
return 0;
}
Thanks Regards
Sinjan
M.Tech(s/w engg)
DTU delhi
On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote:
given a matrix with +ve and -ve numbers, find the submatrix with maximum
sum??
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix
people just dont read the question properly and post the answer
On 9/17/11, prasanth n nprasnt...@gmail.com wrote:
@sinjanspecial:
i think your code is for an 1 D matrix..but i have to find for a 2D matrix..
On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial
sinjanspec...@gmail.comwrote:
hii I think this code will work
#includestdio.h
#includestring.h
void largestsum(int a[],int n)
{
int s=0,e=0,ls=0,max=0,j,i,sum=0;
for(i=0;in;i++)
{
sum+=a[i];
if(summax)
{
max=sum;
e=i;
s=ls;
}
if(sum0)
{
sum=0;
ls=i+1;
}
}
printf(\nlargest sum is=%d\n,max);
printf(The element which make largest sum is\t);
for(j=s;j=e;j++)
{
printf(%d\t,a[j]);
}
}
int main() {
int a[]={6,4,-5,5,2,8,-21,15,4};
int n=9;
largestsum(a,n);
return 0;
}
Thanks Regards
Sinjan
M.Tech(s/w engg)
DTU delhi
On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote:
given a matrix with +ve and -ve numbers, find the submatrix with maximum
sum??
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*
Regards*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the more
successfully u play*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix
@prasanth : sinjalspecial is correct bt his code works for 1D array . for 2D
array you can think of array of 1D array and then implement the same .
newazz here is one link :
http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html
On Sat, Sep 17, 2011 at 8:43 PM, tech coder techcoderonw...@gmail.comwrote:
people just dont read the question properly and post the answer
On 9/17/11, prasanth n nprasnt...@gmail.com wrote:
@sinjanspecial:
i think your code is for an 1 D matrix..but i have to find for a 2D
matrix..
On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial
sinjanspec...@gmail.comwrote:
hii I think this code will work
#includestdio.h
#includestring.h
void largestsum(int a[],int n)
{
int s=0,e=0,ls=0,max=0,j,i,sum=0;
for(i=0;in;i++)
{
sum+=a[i];
if(summax)
{
max=sum;
e=i;
s=ls;
}
if(sum0)
{
sum=0;
ls=i+1;
}
}
printf(\nlargest sum is=%d\n,max);
printf(The element which make largest sum is\t);
for(j=s;j=e;j++)
{
printf(%d\t,a[j]);
}
}
int main() {
int a[]={6,4,-5,5,2,8,-21,15,4};
int n=9;
largestsum(a,n);
return 0;
}
Thanks Regards
Sinjan
M.Tech(s/w engg)
DTU delhi
On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote:
given a matrix with +ve and -ve numbers, find the submatrix with
maximum
sum??
--
*prasanth*
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*prasanth*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*
Regards*
*The Coder*
*Life is a Game. The more u play, the more u win, the more u win , the
more
successfully u play*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix
@Guna: The outer elements are a[i][j] with i = 0 or i = n-1 or j = 0 or j = m-1. Thus, something like this will do the trick: sum=0; for( i = 0 ; i n ; ++i ) sum += a[i][0] + a[i][m-1]; for( j = 1 ; j m-1 ; ++j ) sum += a[0][j] + a[n-1][j]; Dave On Sep 14, 12:35 pm, guna sekaran vgun...@gmail.com wrote: Write a program for adding the outer elements of N*M matrix -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@ shashank and all can we an approach that take less time than O(N^2). I mean not in O(N ) or nlogn but n^2 some optimiation On Thu, Aug 25, 2011 at 8:43 PM, WgpShashan) k shashank7andr...@gmail.com wrote: @Sharvan ..Yes We Can do That and yes i forgot that intead of locals.add(a[i][j]) , we need tow write locals.add(i+j) Hope its fine now :) *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FKYupw3YSG4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix finding immediate neighour
If i got the question correct then its Simple Straightforward, We need to
Check All neighbors, With Boundary conditions
public static ListInteger findLocalMaxima(Integer a[][])
{
ListInteger locals = new ArrayListInteger();
int row=a.length;
for (int i = 0; i row;i++)
{
int col=a[i].length;
for (int j = 0; j col; j++)
{
Integer lm=a[i][j];
Boolean aa= ( lm a[i-1][j-1] ) (i0 j0 );
Boolean b=(lm a[i][j-1]) j0;
Boolean c= (lm a[i-1][j]) i0;
Boolean d= (lm a[i][j+1]) jcol-1;
Boolean e= (lm a[i-1][j+1]) (i0 jcol-1);
Boolean f= (lm a[i+1][j-1]) (irow-1 j0);
Boolean g= (lm a[i+1][j]) irow-1;
Boolean h= (lm a[i+1][j+1]) (irow-1 jcol-1);
if( aa b c d e f g h )
locals.add(a[i][j]);
}
}
return locals;
}
correct me if anything wrong ?
*Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/5xmX_nyPRKkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@Shashank
You can enhance further by moving border condition check for i j before
you access them i.e,
(i0 j0 ) ( lm a[i-1][j-1] ) ;
also location is to be saved not numbers. :)
On Thu, Aug 25, 2011 at 5:35 PM, WgpShashank shashank7andr...@gmail.comwrote:
If i got the question correct then its Simple Straightforward, We need to
Check All neighbors, With Boundary conditions
public static ListInteger findLocalMaxima(Integer a[][])
{
ListInteger locals = new ArrayListInteger();
int row=a.length;
for (int i = 0; i row;i++)
{
int col=a[i].length;
for (int j = 0; j col; j++)
{
Integer lm=a[i][j];
Boolean aa= ( lm a[i-1][j-1] ) (i0 j0 );
Boolean b=(lm a[i][j-1]) j0;
Boolean c= (lm a[i-1][j]) i0;
Boolean d= (lm a[i][j+1]) jcol-1;
Boolean e= (lm a[i-1][j+1]) (i0 jcol-1);
Boolean f= (lm a[i+1][j-1]) (irow-1 j0);
Boolean g= (lm a[i+1][j]) irow-1;
Boolean h= (lm a[i+1][j+1]) (irow-1 jcol-1);
if( aa b c d e f g h )
locals.add(a[i][j]);
}
}
return locals;
}
correct me if anything wrong ?
*Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/5xmX_nyPRKkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@Sharvan ..Yes We Can do That and yes i forgot that intead of locals.add(a[i][j]) , we need tow write locals.add(i+j) Hope its fine now :) *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FKYupw3YSG4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix question ???!!!!!!!!!!??????????
@Anika: You don't have to find the max and min elements of the entire
array to find a row that doesn't contain either of them. If you scan 3
rows, you will find a row that contains the max of those three rows,
another that contains the min, and the remaining row will contain
neither. Scanning the rest of the array would serve only to increase
the maximum and decrease the minimum, but it wouldn't alter the fact
that that remaining row doesn't contain either. Thus, we don't need to
scan the rest of the matrix.
Dave
On Aug 16, 11:23 pm, Anika Jain anika.jai...@gmail.com wrote:
i didnt get it tht even if there are distinct elements how scanning sum
three lines return us the max n min elements? how will this scan whole
matrix for finding the max n min elements???
On Wed, Aug 17, 2011 at 1:32 AM, priya ramesh
love.for.programm...@gmail.com wrote:
are these algos optimal???
*Algo 1*:
no_min_max = -1
min_row = max_row = -1
for(i=0; in; i++)
{
for(j=0; jn; j++){
find min, max
}
if(minprev_min max prev_max){
no_min_max=i;
break;
}
else if(min prev_min){
min_row=i;
}
else if(maxprev_max){
max_row=i;
}
}
if(no_min_max!=-1){
i=0;
while(i!=min_row i!=max_row)
i++;
no_min_max=i;
}
print no_min_max row;
*Algo 2:*
1. Copy elements into a linear array
2. Find min and max. O(n)
3. for(i=0; irows; i++){
serach for min, max in the ith row; O(n)
if (both not found)
break;
}
print the ith row;
Which 1 is better???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix sum
O(nm) preprocessing is required. A[i][j] contains sum of all numbers which lies into a rectangle with bottom right corner at (i, j). To answer the query: decompose rectangles and find the answer via some addition and subtractions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix sum
question is based on simple D.P. use an auxiliary matrix to record the sum of all rectangles we are possible and use this matrix in subsequent quering there is an example 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 this is our original matrix now keep on doing the sum on auxiliary matrix aux[i][j]=aux[i-1][j]+aux[i][j-1]+original[i][j] this is the relation . hope this helps correct me if i m wrong. On Tue, Dec 14, 2010 at 2:52 PM, juver++ avpostni...@gmail.com wrote: O(nm) preprocessing is required. A[i][j] contains sum of all numbers which lies into a rectangle with bottom right corner at (i, j). To answer the query: decompose rectangles and find the answer via some addition and subtractions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: matrix sum
After making the aux array (as written in above post), you can answer any query in O(1) time by using the following relation: assuming top left as (x1,y1) and bottom right as (x2,y2) sum_of_rectangle = aux[x2][y2] - aux[x1-1][y2] - aux[x2][y1-1] + aux[x1-1][y1-1] It may happen that while subtracting 1 from any variable above the value may come out to be negative. That should be handled. Regards. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Matrix Toggling
It seems it is possible to have unreachable destnation matrix. However I have last query. Is it possible to use initial and final matrix to determine if one is reachable from other through toggle operations without actually performing them? _dufus On Sep 19, 8:21 pm, Dufus rahul.dev.si...@gmail.com wrote: Does it means that every M*N matrix is reachable from a given M*N matrix. In other words is it possible that there is no sequence of toggle operation using which the final matrix can be reached? _dufus On Sep 19, 5:54 pm, MrM maleki...@gmail.com wrote: its a beautiful classical problem :) first its easier to find which blocks needs to be toggled ! (it can be done by xor) so your initial matrix changes to : 1 1 0 0 0 1 0 0 1 now we want to set all blocks to 0. its obvious that if we toggle a row or column twice, the result is as same as do nothing ! so we can conclude that each block can be toggled at most twice (once by its row and once by its column). the point in this problem is that there cannot be more than 2 way to change the initial matrix to final matrix ! because if you toggle the first row, you can find that which columns should be toggled (by their common block with first row), and then you can denote the status of remaining rows ! so once you toggle first row and once not ! another point is that both this ways, are the same ! it means if you reached the final state by toggling X rows and columns, you will reach the final state by toggling the remaining 2*N-X rows and columns too ! if you couldn't reach the final state with this way, you can be sure that its impossible to reach the final state ! and if you made it, the minimal number if moves is equal to MIN (X, 2*N - X) you can also use this method for an M*N matrix ! Hope it helps ^-^ On Sep 19, 3:02 pm, Bharath Kumar bharath1...@gmail.com wrote: Given two square matrices(initial and final) consisting of elements either 1 or 0. Using minimum number of toggles change the initial to final matrix. You can toggle either a single row or column at a time. If ith row is toggled all 1's become 0 and vice versa in that row. What will be the correct algorithm for this? For example |0 0 1| |1 1 1| |1 0 1| to |1 1 1| |1 1 0| |1 0 0| would require 1st row and last column toggle. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Matrix Toggling
Nice explanation MrM. Thanks a lot. On Sat, Sep 19, 2009 at 6:24 PM, MrM maleki...@gmail.com wrote: its a beautiful classical problem :) first its easier to find which blocks needs to be toggled ! (it can be done by xor) so your initial matrix changes to : 1 1 0 0 0 1 0 0 1 now we want to set all blocks to 0. its obvious that if we toggle a row or column twice, the result is as same as do nothing ! so we can conclude that each block can be toggled at most twice (once by its row and once by its column). the point in this problem is that there cannot be more than 2 way to change the initial matrix to final matrix ! because if you toggle the first row, you can find that which columns should be toggled (by their common block with first row), and then you can denote the status of remaining rows ! so once you toggle first row and once not ! another point is that both this ways, are the same ! it means if you reached the final state by toggling X rows and columns, you will reach the final state by toggling the remaining 2*N-X rows and columns too ! if you couldn't reach the final state with this way, you can be sure that its impossible to reach the final state ! and if you made it, the minimal number if moves is equal to MIN (X, 2*N - X) you can also use this method for an M*N matrix ! Hope it helps ^-^ On Sep 19, 3:02 pm, Bharath Kumar bharath1...@gmail.com wrote: Given two square matrices(initial and final) consisting of elements either 1 or 0. Using minimum number of toggles change the initial to final matrix. You can toggle either a single row or column at a time. If ith row is toggled all 1's become 0 and vice versa in that row. What will be the correct algorithm for this? For example |0 0 1| |1 1 1| |1 0 1| to |1 1 1| |1 1 0| |1 0 0| would require 1st row and last column toggle. -- Bharath --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Matrix Diff
The matrices already correspond with each other, correct? So a[0]]0]
already should match with b[0][0], right? So if you start sorting,
you'll need to sort both matrices, and not just one column, since the
columns must be kept in their proper relationship with each other, and
since they're enormous, (even with an optimized mergesort), the
sorting itself is a lot of work and time. I definitely wouldn't do
that.
Subtracting as you mention can be used, but a test for equality is no
slower than subtracting and then checking for a zero result.
Matrix checking is very fast, because several elements can be loaded
into the cache at once, and the rest is naturally buffered by the
compiler in RAM, (and then on the disk at least once), so it proceeds
rapidly. (Much faster than a linked list, for example).
I like your overall approach, but I would generalize it across all the
cells:
For each cell in array A[r][c] /* r = row, c = column */
If the cell in array A[r][c] == the cell in array B[r][c]
then print in black: A[r][c], B[r][c].
else
Change print color to red.
print cell's contents.
change print color back to black
end if
end for
You may want to put the unique rows and col's numbers out to a data
file to prevent it just scrolling off the screen and getting lost.
You may discover that you can use flags to prevent the second X
checking of the array's values, but that won't always be possible. I
believe for your situation, there is no special algorithmic speed up
(such as using a hash, or sorting it first, etc.), that can help you.
Don't try to be fancy - simplicity is your friend here. The program
will be able to run very fast if you can avoid the tendency to over-
engineer it.
Try to mimic how YOU would do this work, by hand with paper and
pencil. Humans are very lazy and smart at avoiding inefficient work on
simple tasks.
On Jul 15, 2:34 am, Shark [EMAIL PROTECTED] wrote:
Well its more table then its a matrix, the data is represented in row
row example:
car| manufacture year | engine volume
Volvo | 1996 2002
The data arrives as matrix data structure
What I thought to do:
Run this :
For each row in first table get the element at [i][0]
For each row in second table get element at [j][0]
{
Are element equal?{
For each column in row i in first table mark changes between
j row
in the second table
Break second loop;}
If no matching row found , mark entire row i as missing
}
Once on matrix1, matrix2
And then run it on matrix2,matrix1 (in order to find missing rows in
matrix2)
Also I thought about sorting the matrixes by the rows first element
and then perform minus operation between the matrixes row by row and
get the differences matrix
I am looking for the best and fastest solution because the matrix size
is enormous
Thank you
Sharon
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Matrix Diff
Shark, when you sway the diff should be based on each line, do you mean a horizontal line (row), or a vertical line of data (column)? The red highlight I'm seeing on that link's web page, seems to indicate that each cell in the array, must be checked, since there are differences in each column of the array's, and it seems there could be differences found in any row, as well. I do not (so far), see any way to optimize this comparison of two array's. By paint do you mean highlight the text differences in red, like the example? Are you using Linux or Windows, and what type of Windows(Me, 2000, XP, or Vista)? I'm not a CS grad, just a hobby programmer, Shark. Are you saying that there is a better algorithm than just brute force checking in this problem? If you want to know exactly what the changes are, for instance, a row was removed, then you'll have to add that logic to your matrix checking code (or perhaps in a sub function that it calls as needed). It's far easier to just highlight any changes. On Jul 13, 6:16 am, Shark [EMAIL PROTECTED] wrote: Sorry! Forgot something, the diff should be based on each line For example the first line is black is missing And on the brown line (last one) Michelangelo is different then the one on the second table Thank you --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
