可变数量集合之间的模糊选择

Question

我想知道在以下情况下哪种是获取我需要的内容的最简单和最可配置的方法：

• 我有一个计数器，让我们称之为 X ，它将用于提取
• 我拥有的 集合之一可变数量的集合S1，S2，..，可以被视为总订购 在它们之间
• 我想混合这些集合以模糊的方式，这样对于 X = 0 它将给我 S1，对于，比方说，X = 20 它会给我 < code>S1 的概率为 70%，S2 的概率为 30%
• 增加 X 会降低 S1 的概率直至 0%，而增加S2达到 100%，那么可能存在一个区域，在该区域中它将始终为我提供 S2 直到一个新的阈值，其中 S2 将开始减少，并且 S3 将开始获得机会，依此类推，

我知道如何通过对所有内容进行硬编码来做到这一点，但因为它需要一些调整我想应用一个解决方案，它可以轻松地允许我配置我有多少组和单个阈值（增加概率的开始/结束和减少概率的开始/结束）。当然，我不需要超过 2 个集合之间有任何交集，概率的线性增加/减少就可以了..有什么好的线索吗？

提前致谢！

Answer 1

要分配概率分布，您可以使用 Bernstein 多项式：

http://en.wikipedia.org/wiki /Bernstein_polynomial

这些可以使用 de Casteljau 算法有效地计算（基本上它以明显的方式在递归上进行 DP）：

http://en.wikipedia.org/wiki/De_Casteljau's_algorithm

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

你得到的结果将是一个集合分布上的权重。要选择其中一个集合，您只需在 [0,1] 中生成一个均匀随机变量，然后根据这些权重选择它所在的集合。

下面是 python 中的一些代码，它执行此操作：

import random

#Selects one of the n sets with a weight based on x
def pick_a_set(n, x):

    #Compute bernstein polynomials
    weights = [ [ float(i == j)  for j in range(n) ] for i in range(n) ]
    for k in range(n):
        for j in range(n-k-1):
            for i in range(n):
                weights[j][i] = weights[j][i] * (1.0 - x) + weights[j+1][i] * x

    #Select using weights
    u = random.random()
    for k in range(n):
        if u < weights[0][k]:
            return k
        u -= weights[0][k]
    return 0