合并两组不均匀的项目

Question

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

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

Answer 1

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

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

遍历较大的集合，从累加器（用 number_between 初始化）中的每个循环减去 1，每当累加器低于 0 时从较小的集合中插入一个项目，并用 [= 刷新它13=]:

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 会下溢（你会得到一个完全由较大集合和较小集合的 none 组成的结果）。

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

Answer 2

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 最终均匀分布在整个范围内，这是 "fairly even distribution".[=21= 的统计描述]

您没有指定语言，所以这里是 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

Answer 3

好吧，我一直在研究这个问题，并提出了一个适合我的目的的解决方案。我基本上将较大的项目混合到较小的项目中，然后循环返回，直到我运行出较大的项目。

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

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

合并两组不均匀的项目

Merge two uneven sets of items

distribution

collate