Thread: duplicate detection algorithm

  1. #1
    Registered User
    Join Date
    Nov 2001
    Location
    Mexico City
    Posts
    33

    Thumbs up duplicate detection algorithm

    Hi.

    I've been having troubles with a permutation program. I'm using a module named 'duplicate()' wich tells me when an array of int named 'A' has a duplicate. That is>

    A[1] = 5, A[2] = 3, A[3] = 1 A[4] = 5.

    there is a duplicate here, A[1] = 5 and A[4] = 5

    the function works when the dimension of A is small, say 5 or 6. When the dimension is about 15, the function fails and the program blacks out-

    The module is recursive and it works as follows

    it takes the first element of A (A[1]) and compares it with the following elements to the right (A[2], A[3] etc. if there is a duplicate, the function returns 1. Otherwise it calls itself, but now taking as first element the element at the right, A[2]. and so on.

    The first call from the main program would be duplicate(1)

    I'm posting the following code of 'duplicate()'. OBJECTS is the dimension of A[]


    int duplicate (int i) {
    int j=i+1;

    if (j<=OBJECTS) {
    while ( (A[i]!=A[j]) && (j<=OBJECTS) ) j++;
    if (j>OBJECTS) { // no duplicate
    if (i<OBJECTS)
    return duplicate(i+1);
    else
    return 0; // no duplicate
    }
    else // duplicate
    return 1;

    } // if
    else
    return 0; // no duplicate

    }

    Can anyone tell me why it works when OBJECTS is small and not when it is 14,15....?

    Thanks in advance.
    Last edited by Gustaff; 01-25-2003 at 08:10 PM.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    What is the point of a global array (and size)? You certainly can't reuse your algorithm! The code is fine other than that. A more useful ( ie: reusable ) function however might be:

    Code:
    int duplicate (int array[], int objects, int index) {
    int j = index + 1;
       if (j <= objects)
      {
          while ( (array[index]!= array[j]) && (j <= objects) )
           j++;
    
          if (j > objects)
         {
             if (index < objects)
              return duplicate(array, objects, index + 1);
             else
              return 0;
         }
          else return 1;
      }
       else return 0;
    }

    Of course, unless you are simply being told to use recursion here, it just doesn't make sense. ie:

    Code:
    int duplicate(int array[], int length)
    {
     int i, j;
    
       for(i = 0; i < length-1; ++i)
      {
         for(j = i+1; j < length; ++j)
        {
           if(array[j] == array[i])
          {
            return 1;
          }
        }
      }
     return 0;
    }
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Nov 2001
    Location
    Mexico City
    Posts
    33
    Hi.

    Ichecked the code I posted and now I know that it was an external problem, it was not due to the function duplicate()

    The function I wrote I was just wanted to be used in a program, that's why I used global variables as A[].

    I don't like functions that has a statment 'return' inside a FOR loop, because if you use it many times in a single run, the program will crash. -stack overflow-

    I'm making a program about permutations. I want to process each permutation of 15 objects. Say 1,2,3..15 the total number of permutations is 15! which is a huge number (about 1000 BILLION).

    Do you know a way I can do it? I'm using dev-c++ 4.

    Thanks in advance.

    For the bright side of the worl> Have a good Sunday
    If you want to be happy one hour: take a nap
    if you want to be happy one day: go fishing
    If you want to be happy a year: inherit a fortune
    if you want to be happy for a life time: HELP SOMEBODY
    chinisse say.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    You're confused. Return statements within loops don't cause stack overflows! Recursion can often cause them, but usually only when large arrays are declared recursively, for example. I don't know what a 'permutation' is. Care to explain a little more about it?
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  5. #5
    Registered User
    Join Date
    Nov 2001
    Location
    Mexico City
    Posts
    33

    Thumbs down

    A permutacion is a diferent way to arrange objects. For example if you have 1 and 2 there are two permutations:

    1 2
    2 1

    if you have 1 2 3 you have 6 ways to arrange the numbers:

    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 2 1
    3 1 2

    So, the number of permutations of N objects is N!
    For the first case (2 objects) N=2; N! = 1*2
    For the second case (3 objects) N=3; N!=1*2*3,
    For 4 objects N!= 1*2*3*4, and so on.

    The program I made worked finally, but I made some calculations and would take about a year, so that the computer analyse all 1000 billion permutations.

    If anyone is interested in permutations, I have a recursive and 'normal' code to deal with them.

    Have a good day. Gustaff.
    If you want to be happy one hour: take a nap
    if you want to be happy one day: go fishing
    If you want to be happy a year: inherit a fortune
    if you want to be happy for a life time: HELP SOMEBODY
    chinisse say.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. algorithm for duplicate file checking help
    By geekoftheweek in forum C Programming
    Replies: 1
    Last Post: 04-04-2009, 01:46 PM
  2. Breakout Collision Detection Algorithm Help
    By xmltorrent in forum Game Programming
    Replies: 8
    Last Post: 08-24-2006, 02:32 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM