How to check for duplicates in a dynamic array of elements containing random integers

Problem/Question/Abstract:

Say I have a dynamic array of five elements containing random integers. I want to be able to check for duplicate numbers among the 5 elements and if found, call a random number generator function until all the numbers are different.

Answer:

Solve 1:

This strategy goes through the array one element at a time, making sure it is unique. All we have to do is make sure it is unique from all the preceding elements, and by the time you get to the end of the array, it is all unique.

procedure ForceUnique;
var
  i, j: integer;
begin
  for i := 2 to 5 do {the first element is unique by definition}
  begin
    j := 1;
    while (j < i) do
    begin
      if MyArray[j] = MyArray[i] then
      begin
        MyArray[i] := Random(MyRange);
        j := 1; {start over with a new number}
      end
      else
        j := j + 1;
    end;
  end;
end;

Watch out for potential infinite loop problem if the range of random numbers is less than the size
of the array.


Solve 2:

How about filling the arrays with ascending order of number and then shuffling it randomly afterwards. This is the quickest and surest way to achieve the same effect.

What I am afraid is a situation like this. Let us say you have an array of 32767 small integers. Let us say you want to fill the individual elements with Random values ranging from 0 to 32767. Using random number generator, the probability that all of the elements will be unique is zero. Now, let us say, you sort the random list first, then it is easy to find duplicates, and let us say for each duplicate you try to generate a random number which is not in the array and hopefully replace those duplicates. In this situation, your program will take forever to complete.

If you only have 5 elements, a bubble-type comparison would suffice, if you have more than a hundred elements, you need to sort your array first and do a binary search to find duplicates. If your random number ranges from 0 to MaxInt, this has a greater chance of successfully completing than with a smaller random number range.

Here's the slowest but easy to understand working code for bubble-wise comparisons. Assume iArray is your dynamic array 1 based.

{declare these first:
i, j, k, iRand, iCurr: integer;
iAlreadyExists: boolean;}

{ ... }
for i := 1 to 5 do
begin
  icurr := iArray[i];
  for j := i + 1 to 5 do
  begin
    if icurr = iArray[j] then
    begin
      repeat
        irand := Random(MaxInt);
        iAlreadyExists := False;
        for k := 1 to 5 do
        begin
          if irand = iArray[k] then
          begin
            iAlreadyExists := True;
            break;
          end;
        end;
      until
        not iAlreadyExists;
      iArray[i] := irand;
      break;
    end;
  end;
end;
{ ... }