algorithmrandomada

list of unique random numbers in an Interval in Ada


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?


Solution

  • There's a discussion of implementing the Fisher–Yates shuffle here. Basically, you need a different range of Discrete_Random in each iteration; Float_Random is an alternative, as mentioned in AI12-0144-1. This example illustrates two approaches: If bias isn't critical, the approach seen here or here may be sufficient. If Ada 2022 is available, the new Random overload with range parameters is illustrated here.

    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).