生成与指定百分比成比例的序列的算法

Question

给定对象 map 和指定比例(假设它们加起来为 100 以使其简单):

val ss : Map[String,Double] = Map("A"->42, "B"->32, "C"->26)

如何生成一个序列，使得对于大小为 n 的子集，有 ~42% 的“A”、~32% 的“B”和~26% 的“C”？ (显然，较小的 n 会产生较大的错误)。

(工作语言是Scala，不过我只是求算法。)

更新:我反对随机方法，因为例如，序列以 AA 开头的可能性约为 16%，以 AA 开头的可能性约为 11% BB 并且对于 n 恰好 ==(比例总和)分布是完美的可能性非常低。所以，按照@MvG 的回答，我实现如下:

/**
Returns the key whose achieved proportions are most below desired proportions
*/
def next[T](proportions : Map[T, Double], achievedToDate : Map[T,Double]) : T = {
    val proportionsSum = proportions.values.sum
    val desiredPercentages = proportions.mapValues(v => v / proportionsSum)
    //Initially no achieved percentages, so avoid / 0 
    val toDateTotal = if(achievedToDate.values.sum == 0.0){
        1
    }else{
        achievedToDate.values.sum
    }
    val achievedPercentages = achievedToDate.mapValues(v => v / toDateTotal)
    val gaps = achievedPercentages.map{ case (k, v) =>
        val gap = desiredPercentages(k) - v
        (k -> gap)
    }
    val maxUnder = gaps.values.toList.sortWith(_ > _).head
    //println("Max gap is " + maxUnder)
    val gapsForMaxUnder = gaps.mapValues{v => Math.abs(v - maxUnder) < Double.Epsilon }
    val keysByHasMaxUnder = gapsForMaxUnder.map(_.swap)
    keysByHasMaxUnder(true)
}

/**
Stream of most-fair next element 
*/
def proportionalStream[T](proportions : Map[T, Double], toDate : Map[T, Double]) : Stream[T] = {
    val nextS = next(proportions, toDate)
    val tailToDate = toDate + (nextS -> (toDate(nextS) + 1.0))
    Stream.cons(
        nextS,
        proportionalStream(proportions, tailToDate)
    )
}

当使用时，例如:

val ss : Map[String,Double] = Map("A"->42, "B"->32, "C"->26)
val none : Map[String,Double] = ss.mapValues(_ => 0.0)
val mySequence = (proportionalStream(ss, none) take 100).toList
println("Desired : " + ss)
println("Achieved : " + mySequence.groupBy(identity).mapValues(_.size))
mySequence.map(s => print(s))
println

产生:

Desired : Map(A -> 42.0, B -> 32.0, C -> 26.0)
Achieved : Map(C -> 26, A -> 42, B -> 32)
ABCABCABACBACABACBABACABCABACBACABABCABACABCABACBA
CABABCABACBACABACBABACABCABACBACABABCABACABCABACBA

Answer 1

对于确定性方法，最明显的解决方案可能是这样的:

• 跟踪到目前为止序列中每个项目的出现次数。
• 对于下一项，选择预期计数与实际计数(或比例，如果您愿意)之间的差异最大的项目，但前提是预期计数(相应比例)大于实际计数。
• 如果有平局，以任意但确定的方式打破它，例如选择按字母顺序排列的最低项目。

这种方法将确保以这种方式生成的无限序列的每个前缀都最佳地遵守规定的比率。

快速而肮脏的 python 概念证明(不要指望任何变量“名称”有任何意义):

import sys

p = [0.42, 0.32, 0.26]
c = [0, 0, 0]
a = ['A', 'B', 'C']
n = 0

while n < 70*5:
    n += 1
    x = 0
    s = n*p[0] - c[0]
    for i in [1, 2]:
        si = n*p[i] - c[i]
        if si > s:
            x = i
            s = si
    sys.stdout.write(a[x])
    if n % 70 == 0:
        sys.stdout.write('\n')
    c[x] += 1

生成

ABCABCABACABACBABCAABCABACBACABACBABCABACABACBACBAABCABCABACABACBABCAB
ACABACBACABACBABCABACABACBACBAABCABCABACABACBABCAABCABACBACABACBABCABA
CABACBACBAABCABCABACABACBABCABACABACBACBAACBABCABACABACBACBAABCABCABAC
ABACBABCABACABACBACBAACBABCABACABACBACBAABCABCABACABACBABCABACABACBACB
AACBABCABACABACBACBAABCABCABACABACBABCAABCABACBACBAACBABCABACABACBACBA