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.

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;
}

---

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 :cool:

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?

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.