Author: Jonas Bilinkevicius


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.

1   procedure ForceUnique;
2   var
3     i, j: integer;
4   begin
5     for i := 2 to 5 do {the first element is unique by definition}
6     begin
7       j := 1;
8       while (j < i) do
9       begin
10        if MyArray[j] = MyArray[i] then
11        begin
12          MyArray[i] := Random(MyRange);
13          j := 1; {start over with a new number}
14        end
15        else
16          j := j + 1;
17      end;
18    end;
19  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.

20  {declare these first:
21  i, j, k, iRand, iCurr: integer;
22  iAlreadyExists: boolean;}
23  
24  { ... }
25  for i := 1 to 5 do
26  begin
27    icurr := iArray[i];
28    for j := i + 1 to 5 do
29    begin
30      if icurr = iArray[j] then
31      begin
32        repeat
33          irand := Random(MaxInt);
34          iAlreadyExists := False;
35          for k := 1 to 5 do
36          begin
37            if irand = iArray[k] then
38            begin
39              iAlreadyExists := True;
40              break;
41            end;
42          end;
43        until
44          not iAlreadyExists;
45        iArray[i] := irand;
46        break;
47      end;
48    end;
49  end;
50  { ... }