Geek Answers Handbook

List of unique random numbers in the interval in Ada

I'm sorry to bother you, I know this question was asked quite a lot, but never with Ada ... I was wondering if Ada had a standard library - a way to create a list of unique random numbers (you never pick twice as many numbers) in O (n) In a sense, is there an implementation of the Knut-Fisher-Yeiss algorithm in Hell?

+5
source share
3 answers

It discusses the implementation of Fisher–Yatesshuffle here . Basically, for each iteration, you need a different range Discrete_Random, as shown here ; Float_Randomis an alternative as specified in A.5.2 (50), Note 16 . If the bias is not critical, this example may be sufficient.

In any case, the shuffle is O (n), but the choice may be O (1).

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

+5
source

, : a) 0 1000 ) , .

; .

+2

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

- :

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

More articles:


All Articles