How do I perform a duplicate check in code?

Question

This might be a no-brainer to some, but I'm trying to check if there are any duplicate values in my code.

To be clearer, I am creating 5 variable Integers that randomizes a number once they are created. Let's say they're named i1, i2, i3, i4, i5.

I want to run a loop to check on each other to make sure they don't have any possible duplicates. If they do, I'll re-random the second Integer that's being checked. (e.g if (i1 == i4) { i4.rand(); }) That's to make sure i1 doesn't need to get re-checked against all the previously checked values or being stuck in a long loop until a different number is found.

This is what I'm thinking if it was an entire if else statement : if (i1 == i2), if (i1 == i3), if (i1 == i4), if (i1 == i5), if (i2 == i3), if (i2 == i4), if (i2 == i5), if (i3 == i4), if (i3 == i5), if (i4 == i5)

I know I can probably do it "manually" by creating lots of if / else statements, but is there a better way to do it? It probably isn't very feasible if I increase my Integer limit to 20 and I have to if / else my way through 20 value checks. I know there is, but I just can't remember. Search on Google is turning up nothing (maybe I'm searching for the wrong keywords), which is why I'm asking over here at StackOverflow.

All I want to know is how do I do it, theory-wise (how would you check for duplicates in theory?). The answer doesn't necessarily need to be a workable function.

If you want to create a demo code using the programming language I'm using for this problem, itsExcel VBA. But I think this information would be able to apply theory-wise to a lot of other programming languages, so feel free to write in javascript/jQuery, C++, C#, etc. Just remember to comment!

Answer 1

You are looking for Set;

    Set<Integer> hs = new HashSet<Integer>();
    hs.add(i1);
    if(!hs.add(i2)){
       randomize(i2);
    }

Hope this helps. Let me know, if you have any questions. The above is just a concept of what to do.

To get the logic for your code, it will be

   Set<Integer> hs = new HashSet<Integer>();

    for(int count=0; count<Array.length; count++){  // Store the data into the array and loop
        dataToInsert = Array[count]; 

        while(hs.add(dataToInsert)){
           dataToInsert = randomize(dataToInsert);
        }
     }

Answer 2

Here is a simple way to get your integers assuming you want to generate them in the range from 1 to N

Generate an integer from 1:N Generate an integer from 1:N-1 Generate an integer from 1:N-2 Generate an integer from 1:N-(k-1)

Now interpret these as the position of the integer that you generated (in the set of total available integers for that number) and construct your real integer.

Example, N = 5, k=4
3
1
2
2

i1 = 3
i2 = 1
i3 = 4 (the available integers are 2 4 5)
i4 = 5

Note that this requires the minimum amount of random number generations.

Answer 3

To be clear, what you are attempting is the wrong approach. Theoretically, checking for duplicates and "re-randomizing" when one is found, could execute for an infinitely long time because existing integers could continuously be chosen.

What you should be doing is constructing the collection of integers in such a way that there will be no duplicates in the first place. Dennis Jaheruddin's answer does this. Alternatively, if you have a specific set of integers to choose from (like 1-20), and you simply want them in a random order, you should use a shuffling algorithm. In any event, you should start by searching for existing implementations of these in your language, since it has almost certainly been done before.

Answer 4

What you could do is loop over the List<int> and, for each element x at index i, loop while list.Take(i-1).Contains(x) and replace x with a new random number.

If you simply wanted a relatively inexpensive check that a given List<int> is full of unique numbers, however, you could do something like:

bool areAllUnique = list.Count() != list.Distinct().Count()`

Answer 5

Pseudo-code:

1. Create an empty set S.
2. Generate a pseudo-random number r.
3. If r is in S, go to 2. Else, go to 4.
4. Add R to S.
5. If there are still variables to initialize, go to 2.

Exemplary implementation in Java:

public static void main(String[] args)
{
    System.out.println(getUniqueRandoms(5, 10));
}

public static Set<Integer> getUniqueRandoms(int howMany, int max)
{
    final Set<Integer> uniqueRandoms = new HashSet<Integer>(howMany);
    while (uniqueRandoms.size() < howMany)
    {
        uniqueRandoms.add((int) (Math.random() * max));
    }
    return uniqueRandoms;
}

Output:

[8, 2, 5, 6, 7]

If you would like to have them in array, not in Set, just call toArray() on your Set.

Answer 6

HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0; i < 5; i++)
{
    int x;
    do
    {
        x = random();
    }
    while(!set.Add(x));
}

    int i1 = set.ElementAt(0),
        i2 = set.ElementAt(1),
        i3 = set.ElementAt(2),
        i4 = set.ElementAt(3),
        i5 = set.ElementAt(4);

Answer 7

2 ways I can think of.

1: Looping over all the values in your set and comparing each one to what you're adding.

2: Creating a simplistic version of a hash map:

var set
var map_size
create_set(n):
    set <- array of size n of empty lists
    map_size <- n

add_number(num_to_add):
    if num_to_add not in set[num_to_add % map_size]:
        add num_to_add to set[num_to_add % map_size]
        return success
    else:
        return failure

populate_set():
    loop 5 times:
        i <- random_number()
        while(add_number(i) == failure):
            i <- random_number()

This way, each time you add a number, instead of checking against every other number in your set, you're only checking against at most [max value of integer] / [map size] values. And on average [number of elements in set] / [map size] (I think, correct me if I'm wrong) values.

Answer 8

Try

ArrayList<Integer> list = new ArrayList<Integer>();

while (list.size() < 5)
{
    int i = Math.random() * max;
    if (!list.contains(i))
    {
        list.add(i);
    }
}

and you'll got in list 5 different Integers.

Answer 9

In R is pretty simple...

i <- as.integer(runif(5, 1, 10))

for(l in seq_along(i)){
  while(any(i[l]==i[-l])) # checks each against all the other
    i[l] <- as.integer(runif(1, 1, 10))
}

However in R there is the function sample that picks random elements from a given vector without duplicates ( even though you can choose to have them)

> sample(1:10, 5)
[1] 2 5 1 9 6
> sample(1:10, 5)
[1] 3 5 8 2 1
> sample(1:10, 5)
[1] 8 3 5 9 4
> sample(1:10, 5)
[1]  1  8  9 10  5