occurence problem

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

  1. utab

    utab Guest

    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
    #1
    1. Advertising

  2. utab

    Tosha Guest

    "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
    #2
    1. Advertising

  3. 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
    #3
  4. 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
    #4
  5. utab

    Tosha Guest

    "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
    #5
  6. utab

    Tosha Guest

    "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
    #6
  7. utab

    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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dustin D.
    Replies:
    1
    Views:
    11,178
  2. Mr Ideas Man

    Occurence of Char!

    Mr Ideas Man, Feb 10, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    484
    Terry Burns
    Feb 10, 2006
  3. natG
    Replies:
    4
    Views:
    9,665
  4. Roland
    Replies:
    1
    Views:
    1,541
    Oleg Tkachenko
    Sep 25, 2003
  5. utab
    Replies:
    3
    Views:
    319
    Pavel
    May 8, 2006
Loading...

Share This Page