python - 基于单个随机整数的 Python 中的随机连续列表切片

Question

使用单个随机数和一个列表，您将如何返回该列表的随机切片？

例如，给定列表[0,1,2]，随机连续切片有七种可能性:

1. [ ]
2. [ 0 ]
3. [ 0, 1 ]
4. [ 0, 1, 2 ]
5. [ 1 ]
6. [ 1, 2]
7. [ 2 ]

不是获取随机起始索引和随机结束索引，而是必须有一种方法来生成单个随机数并使用该值计算起始索引和结束/长度。

我需要这样，以确保这 7 种可能性具有相等的概率。

Answer 1

只需固定一个顺序，您可以按照该顺序对所有可能的切片进行排序，然后找出一种方法将所有切片列表中的索引转回切片端点。例如，您使用的顺序可以描述为

• 空切片在所有其他切片之前
• 非空切片按起点排序
• 起点相同的切片按终点排序

因此索引 0 应该返回空列表。索引 1 到 n 应该返回 [0:1] 到 [0:n]。索引 n+1 到 n+(n-1)=2n-1 将是 [1:2] 到 [1: n]; 2n 到 n+(n-1)+(n-2)=3n-3 将是 [2:3] 到 [2:n] 等等。你在这里看到一个模式:给定起点的最后一个索引的形式为 n+(n-1)+(n-2)+(n-3)+…+(n-k)，其中 k 是序列的起始索引。那是一个 arithmetic series ，因此总和为 (k+1)(2n-k)/2=(2n+(2n-1)k-k²)/2。如果您将该术语设置为等于给定索引，并且 solve that对于 k，您会得到一些涉及平方根的公式。然后，您可以使用 ceiling 函数将其转换为与该起点的最后一个索引相对应的 k 的整数值。一旦知道 k，计算终点就相当容易了。

但是上面解中的二次方程让事情变得非常难看。所以你最好使用其他命令。现在我想不出一种方法来避免这样的二次项。 Douglas 在 his answer 中使用的命令不避免平方根，但至少他的平方根有点简单，因为他首先按端点排序。您的问题和我的回答中的顺序称为 lexicographical order , 他的名字叫 reverse lexicographical并且通常更容易处理，因为它不依赖于 n。但由于大多数人首先考虑正常(正向)字典顺序，因此这个答案对许多人来说可能更直观，甚至可能是某些应用程序所需的方式。

这是一段 Python 代码，它按顺序列出了所有序列元素，并按照我描述的方式从索引 i 到端点 [k:m] 进行转换以上:

from math import ceil, sqrt
n = 3
print("{:3} []".format(0))
for i in range(1, n*(n+1)//2 + 1):
    b = 1 - 2*n
    c = 2*(i - n) - 1
    # solve k^2 + b*k + c = 0
    k = int(ceil((- b - sqrt(b*b - 4*c))/2.))
    m = k + i - k*(2*n-k+1)//2
    print("{:3} [{}:{}]".format(i, k, m))

c 中的 - 1 项并非来 self 上面给出的数学公式。它更像是从 i 的每个值中减去 0.5。这确保即使 sqrt 的结果稍微太大，您也不会得到太大的 k。因此，该术语说明了数字不精确的原因，并且应该使整个事情变得非常稳健。

项k*(2*n-k+1)//2是属于起点k-1的最后一个索引，所以i 减去该项就是所考虑的子序列的长度。

您可以进一步简化事情。您可以在循环外执行一些计算，如果您必须重复选择随机序列，这可能很重要。您可以将 b 除以 2，然后在许多其他地方去掉该因子。结果可能如下所示:

from math import ceil, sqrt
n = 3
b = n - 0.5
bbc = b*b + 2*n + 1
print("{:3} []".format(0))
for i in range(1, n*(n+1)//2 + 1):
    k = int(ceil(b - sqrt(bbc - 2*i)))
    m = k + i - k*(2*n-k+1)//2
    print("{:3} [{}:{}]".format(i, k, m))