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 bubbletype 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 bubblewise 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 { ... }
