0

我正在尝试将一组项目相当均匀地分配到另一组中，并且正在寻找一种可以提供帮助的算法。

例如，A 组有 42 项，B 组有 16 项。我想将两个组混合在一起，以便 B 在 A 中相当均匀地分布。所以，合并后的组看起来像：{AA B AAA B AA B AA B AAA.....} 当然，这很容易，如果 A 是 B 的倍数，但根据我的需要，情况并不常见。

4

3 回答 3

0

您可以首先从一组中获取另一组项目之间的项目数：

float number_between = bigger_set.size() / smaller_set.size();

迭代较大的集合，从累加器（用 初始化number_between）中为每个循环减去 1，每当此累加器低于 0 时从较小的集合中插入一个项目，并用 刷新它number_between：

float accumulator = number_between;
foreach(item : bigger_set) {
  result.add(item);
  accumulator = accumulator - 1;
  if (accumulator < 0) {
      result.add(next from smaller_set);
      accumulator = accumulator + number_between;
  } 
}

编辑

改成：

float number_between = (bigger_set.size() +1) / smaller_set.size();

如果您想确保较大的列表同时开始和结束结果列表。

编辑 2

请注意，使用浮点运算可能会引入舍入和下溢错误。

例如，如果您使用 IEEE 单精度（尾数为 24 位 ~ 7 个十进制数字）并且较大的列表比较小的列表大 10^7 或更多，则该行将accumulator = accumulator - 1下溢（您将得到一个完全由较大的集合而不是较小的集合产生的结果）。

此外，四舍五入可能会导致在用尽时尝试从较小的列表中提取更多项目。

于 2015-05-05T21:45:20.140 回答
0

1）您可以连接两个组并从组合组中进行简单采样，例如通过打乱元素并遍历打乱的组合集。

2) 如果您希望按顺序进行，您可以从每个组中以概率size(A) / (size(A) + size(B))和进行采样size(B) / (size(A) + size(B))，其中size(A)和size(B)分别是 A 组和 B 组中尚未被采样的元素的当前数量。换句话说，如果 U 是来自 Uniform(0,1) 随机数生成器的抽取：

if U <= size(A) / (size(A) + size(B))
   randomly draw next observation from A
else
   randomly draw next observation from B

在这两种方法中，A' 和B' 最终均匀分布在整个范围内，这是对“相当均匀分布”的统计描述。

您没有指定语言，因此这里是 Ruby 中这两种方法的具体实现。我已将集合大小减半以保持输出长度合理，显然，由于使用了随机性，每次运行它们都会产生不同的结果。

第一种方法：

a = ['A'] * 21
b = ['B'] * 8
c = (a + b).shuffle
puts c.join(',')

例如，它产生了以下输出：

A,A,A,A,A,B,A,A,A,A,A,B,B,B,A,B,A,A,A,A,A,A,A,A,A,B,B,A,B

第二种方法：

a = ['A'] * 21
b = ['B'] * 8
c = []    
while a.length > 0 || b.length > 0
  c << (rand <= (a.length / (a.length + b.length).to_f) ? a.shift : b.shift)
end    
puts c.join(',')

例如，它产生了以下输出：

A,A,B,A,A,A,B,B,A,A,A,A,A,A,A,B,B,B,A,A,A,B,A,A,A,B,A,A,A
于 2015-05-05T21:45:36.060 回答
0

好吧，我一直在玩这个，并提出了一个适合我的目的的解决方案。我基本上将较大的项目混合到较小的项目中并循环返回，直到我用完较大的项目。

For Each item In smallerList
  mergedList.add(smallerID)
Next

itemsRemaining = biggerList.Count

While itemsRemaining > 0
  index = 0

  For i = 1 To smallerList.Count
    If index >= mergedList.Count or itemsRemaining = 0 Then Continue While

    mergedList.Insert(index , largerID)
    index += 2 + loopCount
    itemsRemaining -= 1
  Next

  loopCount += 1
End While

然后我可以用两个列表中的实际项目替换 ID。

因此，对于我的原始示例（第 1 组有 42 个项目，第 2 组有 16 个项目），我最终得到：

111 2 111 2 111 2 111 2 111 2 111 2 111 2 111 2 111 2 111 2 11 2 11 2 11 2 11 2 11 2 11 2

它有点前置，但就我的目的而言，这会很好。

于 2015-05-05T23:42:47.057 回答