Random distinct numbers in Java

Question

I have a problem generating random edges for not directed graph in Java. The problem is exactly the same as here, but I don't have a randperm function from matlab. I tried with creating a list of size v*(v-1)*0.5, where v is a number of vertices in graph, and shuffling it. However I'm trying to generate 100 million edges in graph with 1 million vertices. The list with about 10e12entries is a real problem. So I need 100 million distinct numbers between 1 and 10e12 and have no idea how to get them.

Is your problem generating *distinct* numbers or generating *very large* numbers? — Manu, Jan 15 '16 at 12:26
Possible duplicate of [Generating very large random numbers java](http://stackoverflow.com/questions/8244691/generating-very-large-random-numbers-java) — Manu, Jan 15 '16 at 12:26
I need large amount of distinct pairs of random numbers ( (a,b) and (b,a) is same pair ) — Julian Rubin, Jan 15 '16 at 13:33

score 0 · Answer 1 · answered Jan 15 '16 at 12:48

If you want a small sub-set of possible values without duplicates, a Set is a better approach. This only has to retain the elements you have seen before to avoid duplicates.

Set<Long> longs = new HashSet<>(100_000_000*10/7); // for a load factor of 0.5
Random rand = new Random();
for (int i = 0; i < 100_000_000; i++) {
    Long l = Math.abs(rand.nextLong() % 1000_000_000_000L);
    if (longs.add(l)) {
       // new long
    } else {
       i--;
    }
}

HashSet uses a lot of memory per entry so a more efficient solution is to use a primitive set such as HashLongSet 100 million longs should use between 1 and 2 GB of memory.

Random distinct numbers in Java

1 Answers1