AND Operation on a two dimensional array

[Mugunth]

What is the most effective way of implementing an AND operation on a
two-d array.
I've an array like,
1 3 5 6 7
2 4 5 6 1
8 6 4 9 2
..
..
..

The result should be another array that contains only 6.

Any ideas?

 

[Victor Bazarov]

What is the most effective way of implementing an AND operation on a
two-d array.

What does that mean to perform AND on an array?

I've an array like,
1 3 5 6 7
2 4 5 6 1
8 6 4 9 2
.
.
.

The result should be another array that contains only 6.
Why?

Any ideas?

Nope.

V

 

[Ivan Novick]

What is the most effective way of implementing an AND operation on a
two-d array.
I've an array like,
1 3 5 6 7
2 4 5 6 1
8 6 4 9 2
The result should be another array that contains only 6.

It seems like you are trying to find a list of numbers which are in
every row of the 2-D array. Is that so?

Regards,
Ivan Novick

 

[Diego Martins]

It seems like you are trying to find a list of numbers which are in
every row of the 2-D array. Is that so?

Regards,
Ivan Novick

O(n^n)

O__O

 

[Tomás Ó hÉilidhe]

What is the most effective way of implementing an AND operation on a
two-d array.

With the bitwise AND operator.

I've an array like,
1 3 5 6 7
2 4 5 6 1
8 6 4 9 2

Since you've given a poor explanation, I can only guess that that's
equivalent to:

T arr[3][5] = { {1,3,5,6,7},{2,4,5,6,1},{8,6,4,9,2} };

The result should be another array that contains only 6.

This one's easy:

T arr[1] = {6};

Any ideas?

A better explanation might beg better replies.

 

[Howard]

O(n^n)

Did you mean O(n^2)? Also, I don't think I get your point.

What algorithm are you considering employing which has that cost? Under
certain conditions, you can answer this question by going through the matrix
just once (but I can never remember if that's O(n), where n is the size of
the array, or O(w*h) where w and h are the width and height).

-Howard

 

[Jim Langston]

What is the most effective way of implementing an AND operation on a
two-d array.
I've an array like,
1 3 5 6 7
2 4 5 6 1
8 6 4 9 2
.
The result should be another array that contains only 6.

Any ideas?

You're not explaining exactly what it is your are trying to accomplish, but
it seems like a non optimal soulution would be:
sort each row
store the first row in an array we'll call working
go through each row and remove from working any value that is not in the row
return whatever is left

You are actually looking for a subset. The subset of the elements that are
in each set (row).

Is this the case?

 

[James Kanze]

You're not explaining exactly what it is your are trying to
accomplish, but it seems like a non optimal soulution would
be:
sort each row
store the first row in an array we'll call working
go through each row and remove from working any value that is
not in the row return whatever is left

Not sure how you can speak about a solution if you (admittedly)
don't know what the problem is. If it's what you think, then
sort each row, then use std::set_intersection. Something like:

typedef std::vector< int >
Row ;
typedef std::vector< Row >
Table ;

Row
findCommonElements(
Table::const_iterator
begin,
Table::const_iterator
end )
{
Row result ;
Table::const_iterator
current = begin ;
if ( current != end ) {
result = *current ;
std::sort( result.begin(), result.end() ) ;
++ current ;
}
while ( current != end ) {
Row tmp1( result ) ;
Row tmp2( *current ) ;
std::sort( tmp2.begin(), tmp2.end() ) ;
result.clear() ;
std::set_intersection(
tmp1.begin(), tmp1.end(),
tmp2.begin(), tmp2.end(),
std::back_inserter( result ) ) ;
++ current ;
}
return result ;
}

You are actually looking for a subset. The subset of the
elements that are in each set (row).

Is this the case?

Your description sounds more like a set intersection, treating
each row as a set.

 

[Jim Langston]

Not sure how you can speak about a solution if you (admittedly)
don't know what the problem is.

That's true. My solution was an algorithm of one of the possible things the
OP was trying to accomplish. The OP was not clear on exactly what he was
trying to do.

If it's what you think, then
sort each row, then use std::set_intersection. Something like:

typedef std::vector< int >
Row ;
typedef std::vector< Row >
Table ;

Row
findCommonElements(
Table::const_iterator
begin,
Table::const_iterator
end )
{
Row result ;
Table::const_iterator
current = begin ;
if ( current != end ) {
result = *current ;
std::sort( result.begin(), result.end() ) ;
++ current ;
}
while ( current != end ) {
Row tmp1( result ) ;
Row tmp2( *current ) ;
std::sort( tmp2.begin(), tmp2.end() ) ;
result.clear() ;
std::set_intersection(
tmp1.begin(), tmp1.end(),
tmp2.begin(), tmp2.end(),
std::back_inserter( result ) ) ;
++ current ;
}
return result ;
}



Your description sounds more like a set intersection, treating
each row as a set.

That's one possible explanation of the OP's post and the one I ran with,
asking if this was in fact what he was trying to accomplish.