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.

Answer 3

I took the liberty of coding it up. You'll need to With Ada.Numerics.Discrete_Random.

   Generic
      Low, High : Integer;
   Package Initialization is
      SubType Element is Integer Range Low..High;
      Function Incrementor Return Element;
      Type Element_Array is Array(Element) of Element;

      Values : Element_Array;
      Procedure Print;
   End Initialization;

   Package Body Initialization is
      Count : Element := Element'Last;

      Function Incrementor Return Element is
      begin
         Return Result : Element:= Count do
            Null;
            Count:= Element'Pred( Result );
         Exception
               When Constraint_Error => Count:= Element'Last;
         End Return;
      end Incrementor;

      Procedure Swap( Index_1, Index_2 : In Integer ) is
         Temp : Constant Element:= Values( Integer(Index_1) );
      begin
         Values( Integer(Index_1) ):= Values( Integer(Index_2) );
         Values( Integer(Index_2) ):= Temp;
      end Swap;

      Procedure Print is
      begin
         Put_Line( "Length: " & Values'Length'Img );
         Put( "(" );
         For Index in Values'First..Integer'Pred(Values'Last) loop
            Put( Values(Index)'Img & ',' );
         end loop;
         Put( Values(Values'Last)'Img );
         Put_Line( ")" );
      end Print;


   Begin
      Shuffle:
      Declare
         Package Random_Element is New
        Ada.Numerics.Discrete_Random( Element );
         Number : Random_Element.Generator;
         Use Random_Element;
      Begin
         Values:= Element_Array'( Others => Incrementor );
         Reset( Number );
         For Index in Element'Range loop
            Swap( Integer(Index), Integer(Random(Number)) );
         end loop;
      End Shuffle;
   End Initialization;

And you can test it out with something like:

   Test:
   Declare
      Package Q is new 
    Initialization( Low => 0, High => 1000 );
   Begin
      Q.Print;
   End Test;