基于单个随机整数在Python中获取列表的随机连续子序列。

Question

使用一个随机数和一个列表，如何返回该列表的一个随机片段？

例如，给定列表[0,1,2]，有 七个 可能的连续随机片段：

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

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

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

- Neil C. Obremski

---

list_slice[random.randint(0,len(list)) :] - letsc

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是序列的起始索引。那是一个算术级数，因此该总和为（k + 1）（2n-k）/ 2 =（2n +（2n-1）k-k²）/ 2。如果将该项设为给定索引，并求解k，则会得到涉及平方根的某个公式。然后，您可以使用天花板函数将其转换为与该起始点的最后一个索引相对应的整数值k。一旦您知道了k，计算终点就很容易了。

但是上面的解决方案中的二次方程使事情变得非常复杂。因此，你可能最好使用其他顺序。现在我想不到任何方法可以避免这样的二次项。道格拉斯在他的答案中使用的顺序不能避免平方根，但由于他首先按终点排序，因此他的平方根会更简单一些。你问题和我的答案中的顺序称为字典序, 他的顺序称为反向字典序，通常更容易处理，因为它不依赖于n。但由于大多数人首先考虑正常（前向）字典序，因此这个答案可能对许多人更直观，甚至可能是一些应用程序所需的方式。

以下是一段Python代码，按顺序列出所有序列元素，并按我上面描述的方式将索引转换为端点[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 项不是来自我上面介绍的数学公式。它更像是从每个 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))

- MvG

Answer 2

这里有一个奇怪的地方，就是将空列表与其他列表视为同等重要。如果列表中有n个元素，则更自然的做法是将空列表赋予0或n+1倍于其他列表的权重。但如果你希望它们具有相同的权重，也可以这样做。

在非空连续子列表中，有n*(n+1)/2种可能性。你可以通过起点和终点来指定这些子列表，起点范围从0到终点，终点范围从0到n-1。

生成一个0到n*(n+1)/2之间的随机整数x。

如果x=0，则返回空列表。否则，x的取值范围是1到n(n+1)/2。

计算e = floor(sqrt(2*x)-1/2)。e的取值为0, 1, 1, 2, 2, 2, 3, 3, 3, 3等。

计算s = (x-1) - e*(e+1)/2。s的取值为0, 0, 1, 0, 1, 2, 0, 1, 2, 3等。

返回从索引s到索引e的区间。

(s,e)的取值为(0,0),(0,1),(1,1),(0,2),(1,2),(2,2)等。

import random
import math

n=10

x = random.randint(0,n*(n+1)/2)

if (x==0):
    print(range(n)[0:0]) // empty set
    exit()

e = int(math.floor(math.sqrt(2*x)-0.5))
s = int(x-1 - (e*(e+1)/2))

print(range(n)[s:e+1]) // starting at s, ending at e, inclusive

- Douglas Zare

---

每当s==e时，您的代码会重复生成空切片。 - MvG

@MvG：我的意思是将[s，e]解释为以索引s开头，以索引e结尾（包括s和e），正如我在正文中所述。我会寻找一种更清晰的打印输出方式。 - Douglas Zare

Answer 3

首先，创建所有可能的切片索引。

例如，[0:0]、[1:1]等是等效的，因此我们只包含其中一个。

最后，随机选择一个索引对，并应用它。

import random

l = [0, 1, 2]

combination_couples = [(0, 0)]
length = len(l)

# Creates all index couples.
for j in range(1, length+1):
    for i in range(j):
        combination_couples.append((i, j))

print(combination_couples)

rand_tuple = random.sample(combination_couples, 1)[0]
final_slice = l[rand_tuple[0]:rand_tuple[1]]

print(final_slice) 

---

为确保我们已经获取了它们所有：

for i in combination_couples:
    print(l[i[0]:i[1]])

或者，通过一些数学运算...

对于一个长度为3的列表，可能的索引号为0到3，即n=4。您有其中的2个，即k=2。第一个索引必须小于第二个索引，因此我们需要计算组合数如此描述。

from math import factorial as f    

def total_combinations(n, k=2):
    result = 1

    for i in range(1, k+1):
        result *= n - k + i
    result /= f(k)
    # We add plus 1 since we included [0:0] as well.
    return result + 1

print(total_combinations(n=4))    # Prints 7 as expected.

- user

---

非常直观，因此非常适合小列表。对于大型列表，生成所有元组可能需要太多的内存，因为元组的数量与原始列表的长度成二次方关系。 - MvG

Answer 4

必须有一种方法来生成一个随机数，并使用该值来确定起始索引和结束/长度。

很难说哪种方法最好，但如果您只对将单个随机数绑定到连续切片感兴趣，则可以使用模数。

给定列表l和单个随机数字r，您可以像这样获取连续的切片：

l[r % len(l) : some_sparkling_transformation(r) % len(l)]

其中 some_sparkling_transformation(r) 是必不可少的。它取决于您的需求，但由于我在您的问题中没有看到任何特殊要求，例如：

l[r % len(l) : (2 * r) % len(l)]

这里最重要的是，切片的左右边缘都与r相关。这使得定义这样的连续切片成为一个问题，因为它们不遵循任何可观察到的模式。上面的例子（使用2 * r）产生的切片总是空列表或者遵循[a : 2 * a]的模式。

让我们运用一些直觉。我们知道我们想要找到一个好的随机表示形式，以连续的切片形式表示数字r。结果发现我们需要找到两个数字：a和b，它们分别是切片的左右边缘。假设r是一个好的随机数（我们喜欢它某种程度上），我们可以说a = r % len(l)是一个好的方法。

现在让我们尝试找到b。生成另一个好的随机数的最佳方法是使用支持种子的随机数生成器（random或numpy）。以下是使用random模块的示例：

import random
def contiguous_slice(l, r):
    random.seed(r)
    a = int(random.uniform(0, len(l)+1))
    b = int(random.uniform(0, len(l)+1))
    a, b = sorted([a, b])
    return l[a:b]

祝你好运并玩得开心！

- Konrad Talik

---

你在帖子末尾的代码将过度呈现具有大 a 的切片，并且还会过度呈现空切片。 - MvG

没错，谢谢！我纠正了大写的 a（我想是吧？），我同意空切片会被过度表示。这里需要稍微不同的方法... - Konrad Talik