list of unique random numbers in an Interval in Ada

Question

I'm sorry to bother you I know this question have been asked quite a lot but never with Ada... I was wondering if there were in the Ada standard library a way to generate a list of unique random numbers (you never pick twice the same number) in O(n) In a way is there an implementation of the Knuth-Fisher-Yates algorithm in Ada?

Answer 1

There's a discussion of implementing the Fisher–Yates shuffle here. Basically, you need a different range of Discrete_Random in each iteration, as shown here; Float_Random is an alternative, as mentioned in A.5.2(50), Note 16. If bias isn't critical, this example may be sufficient.

In any case, shuffling is O(n), but selecting can be O(1).

Addendum: The complexity of creating the set depends on the implementation. For example, Containers.Hashed_Sets, A.18.8(88/2) and Containers.Ordered_Sets, A.18.9(116/2).

Answer 2

Given that you want: a) Random numbers from 0 to 1000 and b) the numbers are not to repeat according to the link you provided, you could do this rather easily.

Just fill an array with the range of values and perform some number of swaps on randomly chosen elements thereof; this guarantees both requirements are upheld.