# duplicate detection algorithm

• 01-25-2003
Gustaff
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....?

• 01-25-2003
Sebastiani
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; }```
• 01-26-2003
Gustaff
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.

For the bright side of the worl> Have a good Sunday :cool:
• 01-26-2003
Sebastiani
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?
• 01-28-2003
Gustaff
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. :o

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

Have a good day. Gustaff.