1

给定一个对象的地图和指定的比例（假设它们加起来是 100 以便于计算）：

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

我怎样才能生成一个序列，使得对于一个大小的子集n有~42%的“A”、~32%的“B”和~26%的“C”？（显然，小n的会有更大的错误）。

（工作语言是 Scala，但我只是要求算法。）

更新：我反对随机方法，因为例如，序列开始的可能性约为 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
4

5 回答 5

3

对于序列中的每一项，计算一个（伪）随机数r ，它在 0（包括）和 100（不包括）之间均匀分布。

  • 如果 0 ≤ r < 42，取A
  • 如果 42 ≤ r < (42+32)，取B
  • 如果 (42+32) ≤ r < (42+32+26)=100，取C
于 2012-07-10T20:23:08.950 回答
3

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

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

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

快速而肮脏的 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
于 2012-07-10T20:28:13.673 回答
1

您的子集中每个条目的数量将与您的地图中的相同，但应用了比例因子。

比例因子为n/100。

因此，如果 n 为 50，您将拥有{ Ax21, Bx16, Cx13 }.

根据您的喜好随机排列顺序。

于 2012-07-10T20:27:14.807 回答
0

最简单的“确定性”[就每个类别的#elements] 解决方案 [IMO] 将是：以预定义的顺序添加元素，然后对结果列表进行洗牌。

首先，map(x)/100 * n从每个元素中添加元素 x 选择如何处理整数算术以避免偏离一个元素]，然后打乱结果列表。

使用fisher-yates shuffle对列表进行洗牌很简单，它在大多数语言中都有实现：例如 java 有Collections.shuffle()，而 C++ 有random_shuffle()

在java中，它会很简单：

int N = 107;
List<String> res = new ArrayList<String>();
for (Entry<String,Integer> e : map.entrySet()) { //map is predefined Map<String,Integer> for frequencies
    for (int i = 0; i < Math.round(e.getValue()/100.0 * N); i++) {
        res.add(e.getKey());
    }
}
Collections.shuffle(res);
于 2012-07-10T20:44:20.383 回答
0

这是不确定的，但给出了接近 MvG 的值分布。它的问题是它可以在一开始就给 AAA。考虑到它如何证明我对 MvG 的异议是错误的（而且我不希望有任何支持），我将它发布在这里是为了完整起见。

现在，如果有人对一个确定性的函数有一个想法，expand并且不会只是复制 MvG 的方法（使calc函数变得无用），我会全力以赴！

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>ErikE's answer</title>
</head>
<body>
<div id="output"></div>
<script type="text/javascript">
if (!Array.each) {
   Array.prototype.each = function(callback) {
      var i, l = this.length;
      for (i = 0; i < l; i += 1) {
         callback(i, this[i]);
      }
   };
}

if (!Array.prototype.sum) {
   Array.prototype.sum = function() {
      var sum = 0;
      this.each(function(i, val) {
         sum += val;
      });
      return sum;
   };
}

function expand(counts) {
   var
      result = "",
      charlist = [],
      l,
      index;
   counts.each(function(i, val) {
      char = String.fromCharCode(i + 65);
      for ( ; val > 0; val -= 1) {
         charlist.push(char);
      }
   });
   l = charlist.length;
   for ( ; l > 0; l -= 1) {
      index = Math.floor(Math.random() * l);
      result += charlist[index];
      charlist.splice(index, 1);
   }
   return result;
}

function calc(n, proportions) {
   var percents = [],
      counts = [],
      errors = [],
      fnmap = [],
      errorSum,
      worstIndex;

   fnmap[1] = "min";
   fnmap[-1] = "max";

   proportions.each(function(i, val) {
      percents[i] = val / proportions.sum() * n;
      counts[i] = Math.round(percents[i]);
      errors[i] = counts[i] - percents[i];
   });

   errorSum = counts.sum() - n;
   while (errorSum != 0) {
      adjust = errorSum < 0 ? 1 : -1;
      worstIndex = errors.indexOf(Math[fnmap[adjust]].apply(0, errors));
      counts[worstIndex] += adjust;
      errors[worstIndex] = counts[worstIndex] - percents[worstIndex];
      errorSum += adjust;
   }
   return expand(counts);
}

document.body.onload = function() {
   document.getElementById('output').innerHTML = calc(99, [25.1, 24.9, 25.9, 24.1]);
};
</script>
</body>
</html>
于 2012-07-11T20:01:44.760 回答