# occurence problem

Discussion in 'C++' started by utab, Feb 16, 2006.

1. ### utabGuest

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)
++count;
}
cout << a << "\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.

utab, Feb 16, 2006

2. ### ToshaGuest

"utab" <> wrote in message
news:...
> 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)
naj = set;
int *done = (int*)malloc(naj*sizeof(int));
for (int i=0 ; i<size ; i++) {
if (done[set] == 1) continue;
int count = 0;
for (int j=0 ; j<size ; j++) {
if (set == set[j])
count++;
}
printf("%d = %d\n",set,count);
done[set] = 1;
}
}

Tosha, Feb 16, 2006

3. ### Maxim YegorushkinGuest

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)
std::cout << i << ": " << c << '\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, Feb 16, 2006
4. ### Maxim YegorushkinGuest

Tosha wrote:
> "utab" <> wrote in message
> news:...
> > 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)
> naj = set;
> int *done = (int*)malloc(naj*sizeof(int));
> for (int i=0 ; i<size ; i++) {
> if (done[set] == 1) continue;
> int count = 0;
> for (int j=0 ; j<size ; j++) {
> if (set == set[j])
> count++;
> }
> printf("%d = %d\n",set,count);
> done[set] = 1;
> }
> }

Invoke the following calls and observe effects:

// case 1
occur(0, 0);

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

Maxim Yegorushkin, Feb 16, 2006
5. ### ToshaGuest

"Maxim Yegorushkin" <> wrote in message
news:...
>
> Tosha wrote:
>> "utab" <> wrote in message
>> news:...
>> > 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)
>> naj = set;
>> int *done = (int*)malloc(naj*sizeof(int));
>> for (int i=0 ; i<size ; i++) {
>> if (done[set] == 1) continue;
>> int count = 0;
>> for (int j=0 ; j<size ; j++) {
>> if (set == set[j])
>> count++;
>> }
>> printf("%d = %d\n",set,count);
>> done[set] = 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, Feb 16, 2006
6. ### ToshaGuest

"utab" <> wrote in message
news:...
> 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 = set;
for (size_t i=0 ; i<new_size ; i++) {
for (size_t j=i+1; j<new_size ; j++) {
if (check == 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 == set[j])
count++;
}
printf(printf_format,check,count);
}
}

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

Tosha, Feb 16, 2006
7. ### Daniel T.Guest

In article <>,
"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
>
> #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)
> ++count;
> }
> cout << a << "\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 == counted[j] ) repeat = true;
}
if ( !repeat ) {
// put a in list of already counted numbers
counted[counted_size] = a;
++counted_size;
// count the occurances of a
int count = 1;
for ( int j = i + 1; j < a_size; ++j ) {
if ( a == a[j] )
++count;
}
std::cout << a << "\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.value, result.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.

Daniel T., Feb 16, 2006