随机生成元组 (A, B) 使得 A + B <= C?

Random generation of tuple (A, B) so that A + B <= C?

在评论中进行讨论后,我必须注意这里使用的术语超出了数学上下文,而不是编程上下文。

如何统一生成自然数 AB 的随机元组,以便 A + B <= C,其中 C 是常数?

满足条件的每个可能的元组应该有相同的生成机会。就本题而言,自然数是指大于或等于1的正整数。


错解(只是为了说明问题):取随机A1C,取随机BAC。这样你得到一个 A = 1 的元组和 A = C 的元组的可能性一样大,但是你有 C 第一类元组和只有一个第二类元组,所以个人这些类型的元组出现的概率不同。

已针对更新的问题进行编辑

生成两个数字:

  • X ~ U(1, C)

  • Y ~ U(1, C - X)

现在掷硬币:

  • 概率为 1/2,A <- X,B <- Y
  • 概率为 1/2,A <- Y,B <- X

对于给定的自然数C,有(C-1) * C / 2个可能的自然数*元组,其中A + B <= C

例如C = 5,10个可能的自然数元组是:

(1,1), (1,2), (1,3), (1,4)
(2,1), (2,2), (2,3)
(3,1), (3,2)
(4,1)

因此您可以在 [1, (C-1) * C / 2] 之间选择一个随机值,并根据该值找到元组。

为了更容易找到元组,想象一下列表加倍,三角形翻转并适合自身:

(1,1), (1,2), (1,3), (1,4), (4,1)
(2,1), (2,2), (2,3), (3,2), (3,1)
(3,1), (3,2), (2,3), (2,2), (2,1)
(4,1), (1,4), (1,3), (1,2), (1,1)

现在您只需要一个随机数用于 [1, C-1] 范围内的行和一个随机数 [1, C]

范围内的列

如果行 + 列 <= C 则 A = 行,B = 列

否则 A = C - 行,B = C + 1 - 列

(*) 按照 OP 给出的 "positive integral starting with 1" 自然数的定义,这不是唯一可能的自然数定义