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;