Velocity Reviews > C++ > occurence problem

# occurence problem

utab
Guest
Posts: n/a

 02-16-2006
Dear all,

I would like to find the occurence of numbers in an array(I solved this
problem before now I could not see the solution) but not with iterators
or vectors I want to apply them later, I tried sth like this

#include <iostream>
#include <string>
#include <vector>

using std::cout;
using std::endl;

int main(){
int a[]={1,1,3,4,5,5,6,7,8,9,7,4,1}; // 13 elements
int count;
int p,f; //previous and following element in the array
int b[13];
for(int i=0;i!=11;i++){ // upto the 13-2=11
count = 0;
if(i==0){
for (int j=i;j!=12;j++){ // upto 13-1=12
if(a[j]==a[i])
++count;
}
cout << a[i] << "\t" << count << endl;
}
else{
p=i; // preceeding
f=i+1; // following

if(a[f]!=a[p]){ // compare following and preceding elements
for (int k=f;k!=12;k++){
if(a[k]==a[f])
++count;
}
cout << a[f] << "\t" << count << endl;
}
}
}
return 0;
}

the output is

1 2
3 1
4 2
5 2
6 1
7 2
8 1
9 1
7 1
4 1

the problem is that lets say if 4 follows 4 then no problem but if 4 4
6 4 then problem I could not find the way to fix that(I only compare
the preceeding and following so if the same element appears and
different from the previous one then it again counts that element. SO I
KNOW MY PROBLEM but NO WAY).

thx.

Tosha
Guest
Posts: n/a

 02-16-2006

"utab" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> Dear all,
>
> ...
>

Here is my solution:
-------------------

void occur(int *set, int size) {
int naj = set[0];
for (int i=0 ; i<size ; i++)
if (naj < set[i])
naj = set[i];
int *done = (int*)malloc(naj*sizeof(int));
for (int i=0 ; i<size ; i++) {
if (done[set[i]] == 1) continue;
int count = 0;
for (int j=0 ; j<size ; j++) {
if (set[i] == set[j])
count++;
}
printf("%d = %d\n",set[i],count);
done[set[i]] = 1;
}
}

Maxim Yegorushkin
Guest
Posts: n/a

 02-16-2006

utab wrote:
> Dear all,
>
> I would like to find the occurence of numbers in an array(I solved this
> problem before now I could not see the solution) but not with iterators
> or vectors I want to apply them later, I tried sth like this

[]

> the problem is that lets say if 4 follows 4 then no problem but if 4 4
> 6 4 then problem I could not find the way to fix that(I only compare
> the preceeding and following so if the same element appears and
> different from the previous one then it again counts that element. SO I
> KNOW MY PROBLEM but NO WAY).

Use a counter array if the element range is small, as [0, 0x100) for
bytes. Use a std::map<> for larger ranges.

#include <iostream>
#include <map>

void count(unsigned char* p, unsigned len)
{
unsigned c[0x100] = {};
while(len--)
++c[*p++];
for(unsigned i = 0; i != 0x100; ++i)
if(c[i])
std::cout << i << ": " << c[i] << '\n';
}

template<class T>
void count(T const* p, unsigned len)
{
std::map<T, unsigned> c;
while(len--)
++c[*p++];
for(typename std::map<T, unsigned>::const_iterator i(c.begin()),
j(c.end()); i != j; ++i)
std::cout << i->first << ": " << i->second << '\n';
}

int main()
{
unsigned char a[] = { 0, 1, 2, 3, 1, 2, 1, 2, 4, 5, 6, 7, 8, 1 };
count(a, sizeof(a));
unsigned b[] = { 0, 1, 2, 3, 1, 2, 1, 2, 4, 5, 6, 7, 8, 1 };
count(b, sizeof(b) / sizeof(*b));
}

Maxim Yegorushkin
Guest
Posts: n/a

 02-16-2006

Tosha wrote:
> "utab" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) oups.com...
> > Dear all,
> >
> > ...
> >

>
> Here is my solution:
> -------------------
>
> void occur(int *set, int size) {
> int naj = set[0];
> for (int i=0 ; i<size ; i++)
> if (naj < set[i])
> naj = set[i];
> int *done = (int*)malloc(naj*sizeof(int));
> for (int i=0 ; i<size ; i++) {
> if (done[set[i]] == 1) continue;
> int count = 0;
> for (int j=0 ; j<size ; j++) {
> if (set[i] == set[j])
> count++;
> }
> printf("%d = %d\n",set[i],count);
> done[set[i]] = 1;
> }
> }

Invoke the following calls and observe effects:

// case 1
occur(0, 0);

// case 2
int b[] = { 0, 0x7fffffff };
occur(b, 2);

Tosha
Guest
Posts: n/a

 02-16-2006

"Maxim Yegorushkin" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
>
> Tosha wrote:
>> "utab" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) oups.com...
>> > Dear all,
>> >
>> > ...
>> >

>>
>> Here is my solution:
>> -------------------
>>
>> void occur(int *set, int size) {
>> int naj = set[0];
>> for (int i=0 ; i<size ; i++)
>> if (naj < set[i])
>> naj = set[i];
>> int *done = (int*)malloc(naj*sizeof(int));
>> for (int i=0 ; i<size ; i++) {
>> if (done[set[i]] == 1) continue;
>> int count = 0;
>> for (int j=0 ; j<size ; j++) {
>> if (set[i] == set[j])
>> count++;
>> }
>> printf("%d = %d\n",set[i],count);
>> done[set[i]] = 1;
>> }
>> }

>
> Invoke the following calls and observe effects:
>
> // case 1
> occur(0, 0);

Well, i supose it's shouldn't be a problem to put zero check at beggining of
function.
if (set==0)
return;

>
> // case 2
> int b[] = { 0, 0x7fffffff };
> occur(b, 2);
>

Yes, it doesn't work for numbers larger than 2^30 or somethink like that.

Tosha
Guest
Posts: n/a

 02-16-2006

"utab" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> Dear all,
>
> I would like to find the occurence of numbers in an array(I solved this
> problem before now I could not see the solution) but not with iterators
> or vectors I want to apply them later, I tried sth like this>
>...
>

Try this... there should be no limits unless your set element is above
(2^64)-1

#include <cstdio>
#include <cstdlib>

typedef unsigned __int64 _int;

template <class type>
void occur(type *set, size_t size,char *printf_format) {
if (set==0) return;
type *check = (type*)malloc(size*sizeof(type));
size_t new_size = size;
for (size_t i=0 ; i<size ; i++) check[i] = set[i];
for (size_t i=0 ; i<new_size ; i++) {
for (size_t j=i+1; j<new_size ; j++) {
if (check[i] == check[j]) {
for (size_t k=j ; k<new_size-1 ; k++)
check[k] = check[k+1];
new_size--;
check = (type*)realloc(check,new_size*sizeof(type));
}
}
}
for (size_t i=0 ; i<new_size ; i++) {
type count = 0;
for (size_t j=0 ; j<size ; j++) {
if (check[i] == set[j])
count++;
}
printf(printf_format,check[i],count);
}
}

int main()
{
_int
a[]={18446744073709551615,1,1,3,4,5,5,6,7,8,9,7,4,1,1 8446744073709551615};
occur<_int>(a,15,"%I64u = %I64u\n");
}

Daniel T.
Guest
Posts: n/a

 02-16-2006
In article <(E-Mail Removed) .com>,
"utab" <(E-Mail Removed)> wrote:

> Dear all,
>
> I would like to find the occurence of numbers in an array(I solved this
> problem before now I could not see the solution) but not with iterators
> or vectors I want to apply them later, I tried sth like this
>
> #include <iostream>
> #include <string>
> #include <vector>
>
> using std::cout;
> using std::endl;
>
> int main(){
> int a[]={1,1,3,4,5,5,6,7,8,9,7,4,1}; // 13 elements
> int count;
> int p,f; //previous and following element in the array
> int b[13];
> for(int i=0;i!=11;i++){ // upto the 13-2=11
> count = 0;
> if(i==0){
> for (int j=i;j!=12;j++){ // upto 13-1=12
> if(a[j]==a[i])
> ++count;
> }
> cout << a[i] << "\t" << count << endl;
> }
> else{
> p=i; // preceeding
> f=i+1; // following
>
> if(a[f]!=a[p]){ // compare following and preceding elements
> for (int k=f;k!=12;k++){
> if(a[k]==a[f])
> ++count;
> }
> cout << a[f] << "\t" << count << endl;
> }
> }
> }
> return 0;
> }

Try this:

int main() {
const int a_size = 13;
int a[]={1,1,3,4,5,5,6,7,8,9,7,4,1}; // 13 elements
int counted[a_size];
int counted_size = 0;
for ( int i = 0; i < a_size; ++i ) {
// check for repeat number
bool repeat = false;
for ( int j = 0; j < counted_size && !repeat; ++j ) {
if ( a[i] == counted[j] ) repeat = true;
}
if ( !repeat ) {
// put a[i] in list of already counted numbers
counted[counted_size] = a[i];
++counted_size;
// count the occurances of a[i]
int count = 1;
for ( int j = i + 1; j < a_size; ++j ) {
if ( a[i] == a[j] )
++count;
}
std::cout << a[i] << "\t" << count << '\n';
}
}
}

But here's how I would do it. I like to separate the output from the
computation so 'value_count' is the function that actually counts how
many of each number are in the set, whereas 'main' outputs the result.

typedef struct {
int value;
int count_of;
} assoc;

int value_count( const int* set, int size, assoc** out ) {
int out_cap = 2;
int out_size = 0;
*out = (assoc*)malloc( sizeof( assoc ) * out_cap );
if ( !out ) throw std::bad_alloc();
while ( size-- ) {
bool repeat = false;
for ( int j = 0; j < out_size && !repeat; ++j ) {
if ( *set == (*out)[j].value ) {
++(*out)[j].count_of;
repeat = true;
}
}
if ( !repeat ) {
if ( out_size == out_cap ) {
out_cap = static_cast<int>( out_cap * 1.5 );
*out = (assoc*)realloc( *out, sizeof( assoc ) * out_cap );
if ( !out ) throw std::bad_alloc();
}
(*out)[out_size].value = *set;
(*out)[out_size].count_of = 1;
++out_size;
}
++set;
}
return out_size;
}

int main() {
int a[]={1,1,3,4,5,5,6,7,8,9,7,4,1}; // 13 elements
assoc* result = 0;
int out_size = value_count( a, 13, &result );
for ( int i = 0; i < out_size; ++i )
printf( "%d\t%d\n", result[i].value, result[i].count_of );
free( result );
}

the output is:

1 3
3 1
4 2
5 2
6 1
7 2
8 1
9 1

Of course, this would be trivial (and more flexable) in c++
rather than c.

struct map_value_outputer {
ostream& os;
map_value_outputer( ostream& o ): os( o ) { }
template < typename X, typename Y >
void operator()( const pair< X, Y >& v ) {
os << v.first << "\t" << v.second << '\n';
}
};

int main() {
int a[]={1,1,3,4,5,5,6,7,8,9,7,4,1}; // 13 elements
map<int, int> result;
for ( int* p = a; p != a + 13; ++p )
++result[*p];
for_each( result.begin(), result.end(), map_value_outputer( cout ) );
}

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.