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

Question

给出一张对象和指定比例的地图(假设它们加起来是100，这样就容易了)：

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

如何生成一个序列，使一个大小的n子集有~42%的"A"s，~32%的"B"s和~26%的"C"s？(显然，小n会有更大的错误)。

(工作语言是Scala，但我只是要求算法。)

UPDATE：我抵制一种随机方法，因为例如，有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

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

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

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

快速和肮脏的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

Answer 2

对于序列中的每一项，计算在0(包括)和100 (排他性)之间的(伪随机数r)。

• 如果0 A r< 42，取≤
• 如果42 42+32 r<( B )，取B
• 如果(42+32)≤r< (42+32+26)=100，取C

Answer 3

子集中每个条目的数量将与映射中相同，但需要应用缩放因子。

标度因子为n/100。

如果n是50，你就会得到{ Ax21, Bx16, Cx13 }。

根据你的喜好随机排序。