是否有一个定理，其涉及计算组合物体的总数与随机拾取一个组合物体？

Question

常见的算法挑战是以随机均匀地生成某种物体的对象。例如，生成大小的随机排列 $ k $ 的 $ n $ 字符，如这个问题。

我注意到，当解决这样的任务时，可以通过复制关系计算这种任务的任何算法，以便通过复发关系转换为生成的算法组合物体。我的问题是，这个技术有一个名称吗？是否有一个定理说，当这是真的？

例如，假设我想生成 $ n $ $ 1的随机序列$ s和 $ 0 $ s，其中没有两个相邻的 $ 1 $ s。我可以首先让 $ a [n] $ 是此类序列的数量，并观察到这一点 $$ a [n]= a [n-1] + a [n-2]。 $$

（这是fibonacci关系。） 这使我能够有效地计算 $ a [i] $ for $ i= 1 $ $ i= n $ 。 现在，如果我想生成随机这样的序列，我所要做的就是：

步骤1：生成随机值 $ r $ from $ 1 $ 到 $ a [n] $ 。

步骤2：使用重复关系来定位对应于 $ r $ th序列的子项：

• 如果 $ r \ le a [n-1] $ ，则递归查找 $ r $ < / span> th序列由 $ a [n-1] $ ，并附加a $ 0 $ 。

• 否则，如果 $ a [n-1] ，set $ r'= r - a [n-1] $ ，递归查找 $ r'$ th序列由 $ a [n-2] $ ，并附加a $ 01 $ 。

这里似乎是什么，给定 $ a [n] $ 的任何复发关系，我可以将其转换为递归算法，返回 $ r $ th对象由 $ a [n] $ 。我假设这是众所周知的，所以我对此的任何引用或经典结果都感兴趣。特别是，这不仅仅是特定于示例 $ a [n] $ ，但应该为满足某些问题的任何复发关系属性。

此外，我认为这可能与随机测试的一些研究有关。

Answer 1

这些称为排名和unlanning函数。您对计数和输送算法复发关系之间的对应关系是正确的。