список уникальных случайных чисел в интервале в Аде - PullRequest
Новая
       5

список уникальных случайных чисел в интервале в Аде

5 голосов
/ 19 марта 2011

Извините, что беспокою вас, я знаю этот вопрос задавали довольно много, но никогда не с Ада ... Мне было интересно, есть ли в стандартной библиотеке Ада способ генерировать список уникальных случайных чисел (вы никогда не выбираете дважды одно и то же число) в O (n) В каком-то смысле есть реализация алгоритма Кнута-Фишера-Йейтса в Аде?

Ответы [ 3 ]

5 голосов
/ 20 марта 2011

Здесь обсуждается реализация Fisher–Yates shuffle здесь . По сути, вам нужен другой диапазон Discrete_Random в каждой итерации, как показано здесь ; Float_Random является альтернативой, как указано в A.5.2 (50), примечание 16 . Если смещение не критично, этого примера может быть достаточно.

В любом случае тасование равно O (n) , но выбор может быть O (1) .

Приложение: Сложность создания набора зависит от реализации . Например, Containers.Hashed_Sets, A.18.8 (88/2) и Containers.Ordered_Sets, A.18.9 (116/2) .

2 голосов
/ 20 марта 2011

Учитывая, что вы хотите: а) Случайные числа от 0 до 1000 а также б) цифры не должны повторяться по предоставленной вами ссылке вы можете сделать это довольно легко.

Просто заполните массив диапазоном значений и выполните некоторое количество перестановок для случайно выбранных его элементов; это гарантирует соблюдение обоих требований.

1 голос
/ 24 марта 2011

Я взял на себя смелость его кодировать. Вам понадобится С 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;
...