Ada 中某个时间间隔内的唯一随机数列表

Question

很抱歉打扰你，我知道这个问题已经被问过很多次了，但从来没有问过 Ada...我想知道 Ada 标准库中是否有一种方法来生成唯一随机数列表（你永远不要在 O(n) 中选择两次相同的数字 在某种程度上，Ada 中是否有 Knuth-Fisher-Yates 算法的实现？

Answer 1

这里讨论了实施

Fisher–Yates随机播放。基本上，每次迭代都需要不同范围的 Discrete_Random； Float_Random 是一种替代方案，如 AI12-0144-1 中所述。这个示例说明了两种方法：如果偏差不重要，那么这里或这里看到的方法可能就足够了。如果 Ada 2022 可用，则会在此处

说明新的 

Random 与范围参数的重载。

无论如何，

洗牌都是O(n)，但是选择可以是O(1)。

附录：

创建集合的复杂性取决于实现。例如，Containers.Hashed_Sets、A.18.8(88/2) 和 Containers.Ordered_Sets、A.18.9(116/2).

Answer 2

鉴于您想要： a) 0 到 1000 之间的随机数 和 b) 数字不能重复 根据您提供的链接，您可以相当轻松地做到这一点。

只需用值范围填充一个数组，并对其随机选择的元素执行一定数量的交换；这保证了这两个要求都得到满足。

Answer 3

我冒昧地对其进行了编码。 您需要使用 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;