jjzjj

php - 从可变权重随机生成组合

coder 2024-04-13 原文

非常重要的编辑:所有 Ai 都是独一无二的。

问题

我有一个 A n unique 对象列表。每个对象 Ai 都有一个可变百分比 Pi。

我想创建一个算法，生成 k 个对象的新列表 B (k n/2 并且在大多数情况下 k 明显小于 n/2。例如 n=231，k=21)。列表 B 不应有重复项，并将填充来自列表 A 的对象，但有以下限制:

The probability that an object Ai appears in B is Pi.

我尝试过的

(这些 snipits 在 PHP 中只是为了测试目的) 我首先列出了 A

$list = [
    "A" => 2.5, 
    "B" => 2.5, 
    "C" => 2.5, 
    "D" => 2.5, 
    "E" => 2.5, 
    "F" => 2.5, 
    "G" => 2.5, 
    "H" => 2.5, 
    "I" => 5,   
    "J" => 5,   
    "K" => 2.5, 
    "L" => 2.5, 
    "M" => 2.5, 
    "N" => 2.5, 
    "O" => 2.5, 
    "P" => 2.5, 
    "Q" => 2.5, 
    "R" => 2.5, 
    "S" => 2.5, 
    "T" => 2.5, 
    "U" => 5,   
    "V" => 5,   
    "W" => 5,   
    "X" => 5,   
    "Y" => 5,   
    "Z" => 20   
];

起初我尝试了以下两种算法(这些算法只是为了测试目的而用 PHP 编写的):

$result = [];

while (count($result) < 10) {
    $rnd = rand(0,10000000) / 100000;

    $sum = 0;
    foreach ($list as $key => $value) {
        $sum += $value;
        if ($rnd <= $sum) {
            if (in_array($key,$result)) {
                break;
            } else {
                $result[] = $key;
                break;
            }
        }
    }
}

和

$result = [];

while (count($result) < 10) {
    $sum = 0;
    foreach ($list as $key => $value) {
        $sum += $value;
    }

    $rnd = rand(0,$sum * 100000) / 100000;

    $sum = 0;
    foreach ($list as $key => $value) {
        $sum += $value;
        if ($rnd <= $sum) {
            $result[] = $key;
            unset($list[$key]);
            break;
        }
    }
}

这两种算法之间的唯一区别在于，一种算法在遇到重复项时会重试，而另一种算法会在对象表单列表 A 被选中时将其删除。事实证明，这两种算法具有相同的概率输出。

我将第二个算法运行了 100,000 次，并记录了每个字母被选中的次数。以下数组包含根据 100,000 次测试在任何列表 B 中选择一个字母的百分比机会。

[A] => 30.213
[B] => 29.865
[C] => 30.357
[D] => 30.198
[E] => 30.152
[F] => 30.472
[G] => 30.343
[H] => 30.011
[I] => 51.367
[J] => 51.683
[K] => 30.271
[L] => 30.197
[M] => 30.341
[N] => 30.15
[O] => 30.225
[P] => 30.135
[Q] => 30.406
[R] => 30.083
[S] => 30.251
[T] => 30.369
[U] => 51.671
[V] => 52.098
[W] => 51.772
[X] => 51.739
[Y] => 51.891
[Z] => 93.74

回顾算法时，这是有道理的。该算法错误地将原始百分比解释为对象在任何给定位置(而不是任何列表B)被选中的概率百分比。因此，例如，在现实中，Z 在列表 B 中被选中的几率是 93%，但是 Z 被选中用于索引 Bn 的几率 为 20%。这不是我想要的。我希望 Z 在列表 B 中被选中的几率为 20%。

这可能吗？怎么做到的？

编辑 1

我尝试简单地让所有 Pi 的总和 = k，如果所有 Pi 这有效是相等的，但在修改它们的值后，它开始变得越来越错误。

初始概率

$list= [
    "A" => 8.4615,
    "B" => 68.4615,
    "C" => 13.4615,
    "D" => 63.4615,
    "E" => 18.4615,
    "F" => 58.4615,
    "G" => 23.4615,
    "H" => 53.4615,
    "I" => 28.4615,
    "J" => 48.4615,
    "K" => 33.4615,
    "L" => 43.4615,
    "M" => 38.4615,
    "N" => 38.4615,
    "O" => 38.4615,
    "P" => 38.4615,
    "Q" => 38.4615,
    "R" => 38.4615,
    "S" => 38.4615,
    "T" => 38.4615,
    "U" => 38.4615,
    "V" => 38.4615,
    "W" => 38.4615,
    "X" => 38.4615,
    "Y" =>38.4615,
    "Z" => 38.4615
];

10,000 次运行后的结果

Array
(
    [A] => 10.324
    [B] => 59.298
    [C] => 15.902
    [D] => 56.299
    [E] => 21.16
    [F] => 53.621
    [G] => 25.907
    [H] => 50.163
    [I] => 30.932
    [J] => 47.114
    [K] => 35.344
    [L] => 43.175
    [M] => 39.141
    [N] => 39.127
    [O] => 39.346
    [P] => 39.364
    [Q] => 39.501
    [R] => 39.05
    [S] => 39.555
    [T] => 39.239
    [U] => 39.283
    [V] => 39.408
    [W] => 39.317
    [X] => 39.339
    [Y] => 39.569
    [Z] => 39.522
)

最佳答案

我们必须有sum_i P_i = k，否则我们无法成功。

如前所述，问题有点简单，但您可能不喜欢这个答案，理由是它“不够随机”。

Sample a uniform random permutation Perm on the integers [0, n)
Sample X uniformly at random from [0, 1)
For i in Perm
    If X < P_i, then append A_i to B and update X := X + (1 - P_i)
    Else, update X := X - P_i
End

您需要使用定点运算而不是浮点来近似涉及实数的计算。

缺少的条件是分布具有称为“最大熵”的技术属性。像阿米特一样，我想不出一个好的方法来做到这一点。这是一个笨拙的方法。

我解决这个问题的第一个(也是错误的)直觉是将每个 A_i 独立地包含在 B 中，概率为 P_i 并重试直到 B 是正确的长度(不会重试太多次，原因你可以问 math.SE)。问题是条件反射打乱了概率。如果 P_1 = 1/3 和 P_2 = 2/3 和 k = 1，则结果为

{}: probability 2/9
{A_1}: probability 1/9
{A_2}: probability 4/9
{A_1, A_2}: probability 2/9,

A_1 的条件概率实际上是 1/5，A_2 的条件概率是 4/5。

相反，我们应该替换产生适当条件分布的新概率 Q_i。我不知道 Q_i 的封闭形式，所以我建议使用像 gradient descent 这样的数值优化算法来找到它们。 .初始化 Q_i = P_i(为什么不呢？)。使用动态规划，对于 Q_i 的当前设置，有可能找到在给定具有 l 元素的结果的情况下，A_i 的概率是这些元素之一。 (我们只关心 l = k 条目，但我们需要其他条目来使递归工作。)再做一点工作，我们可以获得整个梯度。抱歉，这太粗略了。

在 Python 3 中，使用似乎总是收敛的非线性求解方法(将每个 q_i 同时更新为其边缘正确的值并归一化):

#!/usr/bin/env python3
import collections
import operator
import random


def constrained_sample(qs):
    k = round(sum(qs))
    while True:
        sample = [i for i, q in enumerate(qs) if random.random() < q]
        if len(sample) == k:
            return sample


def size_distribution(qs):
    size_dist = [1]
    for q in qs:
        size_dist.append(0)
        for j in range(len(size_dist) - 1, 0, -1):
            size_dist[j] += size_dist[j - 1] * q
            size_dist[j - 1] *= 1 - q
    assert abs(sum(size_dist) - 1) <= 1e-10
    return size_dist


def size_distribution_without(size_dist, q):
    size_dist = size_dist[:]
    if q >= 0.5:
        for j in range(len(size_dist) - 1, 0, -1):
            size_dist[j] /= q
            size_dist[j - 1] -= size_dist[j] * (1 - q)
        del size_dist[0]
    else:
        for j in range(1, len(size_dist)):
            size_dist[j - 1] /= 1 - q
            size_dist[j] -= size_dist[j - 1] * q
        del size_dist[-1]
    assert abs(sum(size_dist) - 1) <= 1e-10
    return size_dist


def test_size_distribution(qs):
    d = size_distribution(qs)
    for i, q in enumerate(qs):
        d1a = size_distribution_without(d, q)
        d1b = size_distribution(qs[:i] + qs[i + 1 :])
        assert len(d1a) == len(d1b)
        assert max(map(abs, map(operator.sub, d1a, d1b))) <= 1e-10


def normalized(qs, k):
    sum_qs = sum(qs)
    qs = [q * k / sum_qs for q in qs]
    assert abs(sum(qs) / k - 1) <= 1e-10
    return qs


def approximate_qs(ps, reps=100):
    k = round(sum(ps))
    qs = ps[:]
    for j in range(reps):
        size_dist = size_distribution(qs)
        for i, p in enumerate(ps):
            d = size_distribution_without(size_dist, qs[i])
            d.append(0)
            qs[i] = p * d[k] / ((1 - p) * d[k - 1] + p * d[k])
        qs = normalized(qs, k)
    return qs


def test(ps, reps=100000):
    print(ps)
    qs = approximate_qs(ps)
    print(qs)
    counter = collections.Counter()
    for j in range(reps):
        counter.update(constrained_sample(qs))
    test_size_distribution(qs)
    print("p", "Actual", sep="\t")
    for i, p in enumerate(ps):
        print(p, counter[i] / reps, sep="\t")


if __name__ == "__main__":
    test([2 / 3, 1 / 2, 1 / 2, 1 / 3])

关于php - 从可变权重随机生成组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31019777/

可变phpcode34gtalgorithmprobability

有关php - 从可变权重随机生成组合的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  3. ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2

    我正在编写一个小脚本来定位aws存储桶中的特定文件，并创建一个临时验证的url以发送给同事。(理想情况下，这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针，它似乎不符合这个标准，但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A

  4. ruby-on-rails - Ruby on Rails - 为文本区域和图片生成列 - 2

    我是Rails的新手，所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格，我想要的三列是:公司名称、公司描述和Logo。对于名称，我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串，然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列？ 最佳答案 对于“文本”数

  5. ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL？ - 2

    我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些

  6. ruby-on-rails - 如何在 Rails 3 中创建自定义脚手架生成器？ - 2

    有这些railscast。http://railscasts.com/episodes/218-making-generators-in-rails-3有了这个，你就会知道如何创建样式表和脚手架生成器。http://railscasts.com/episodes/216-generators-in-rails-3通过这个，您可以了解如何添加一些文件来修改脚手架View。我想把两者结合起来。我想创建一个生成器，它也可以创建脚手架View。有点像RyanBates漂亮的生成器或web_app_themegem(https://github.com/pilu/web-app-theme)。我

  7. 报告回顾丨模型进化狂飙，DetectGPT能否识别最新模型生成结果？ - 2

    导读语言模型给我们的生产生活带来了极大便利，但同时不少人也利用他们从事作弊工作。如何规避这些难辨真伪的文字所产生的负面影响也成为一大难题。在3月9日智源Live第33期活动「DetectGPT：判断文本是否为机器生成的工具」中，主讲人Eric为我们讲解了DetectGPT工作背后的思路——一种基于概率曲率检测的用于检测模型生成文本的工具，它可以帮助我们更好地分辨文章的来源和可信度，对保护信息真实、防止欺诈等方面具有重要意义。本次报告主要围绕其功能，实现和效果等展开。（文末点击“阅读原文”，查看活动回放。）Ericmitchell斯坦福大学计算机系四年级博士生，由ChelseaFinn和Chri

  8. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  9. ruby - 最多 n 的组合 - 2

    给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我

  10. python - 帮我找到合适的 ruby​​/python 解析器生成器 - 2

    我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby​​编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby​​。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的

随机推荐