将不同的项目均匀地放置在数组中

Question

我想知道是否有可能以某种方式对数组中的项目进行“排序”以将它们放置在“相等”的间距中。

一个例子超过几百字所以：

Apple - 1
Banana - 2
Pineapple - 3
Orange - 4

这是一个数组：

[ 'Apple', 'Apple', 'Banana', 'Pineapple', 'Pineapple', 'Pineapple', 'Orange' ]
[ 1, 1, 2, 3, 3, 3, 4 ]

我想要实现的是类似这样的东西：

[ 'Apple', 'Pineapple', 'Banana', 'Apple', 'Pineapple', 'Orange', 'Pineapple' ]
[ 1, 3, 2, 1, 3, 4, 3 ]

通过此转换 Pineapple 在其他 'Pineapple' 和 Apple 之间有 1 个项目偏移量被放置在 [0] 和 [3] 位置。

在我开始实施之前，我正在寻找一个已经发明的解决方案 - 它应该与标准差有关？

Answer 1

首先按出现次数对单词进行排序。然后遍历它们，首先填充所有偶数索引，然后填充所有奇数索引。
第一个词最多可以填满所有偶数索引。在大多数现代阵列中，具有偶数索引的槽应始终至少与具有奇数索引的槽一样多。如果您的语言不符合要求（即 one-based 数组），请根据可用插槽的数量选择偶数或奇数。
第二个最常见的词最多只能出现与最常见的词一样多的次数，所以同一个词不可能以这种方式出现在两个相邻的槽位中。
一个简单的 python-implementation 看起来像这样：

import math

def spaced_ordering(words):
    words = sorted(words, key=words.count, reverse=True)
    output = [None] * len(words)

    for i in range(0, math.ceil(len(words) / 2)):
        output[i * 2] = words[i]

    for i in range(0, math.floor(len(words) / 2)):
        output[i * 2 + 1] = words[math.ceil(len(words) / 2) + i]

    return output

注意：上面的实现既不完全高效，也不完全花哨，也不包括检查有效输入（例如，如果一个词出现超过 math.ceil(len(words) / 2) 次会发生什么）。仅用于演示基本原理。

Answer 2

您正在寻找的 class 算法称为多路复用。多路复用器接受多个输入流，并创建一个输出流，一次从输入中选择一个项目。有许多不同的多路复用策略。我将介绍一种易于实施且性能良好的方法。

大意是每个项目都有一个名称、比率和累加器 ，然后选择其累加器中具有最大值的项目。在问题中给出的示例中，Apple 的费率是 2，Banana 的费率为 1，Pineapple 的费率为 3，Orange 的费率为 1。利率之和就是周期，即7.

算法运行如下：

initialize all accumulators to 0
for each slot in one period:
    choose the item with the largest accumulator, and add it to the output
    update each accumulator by adding the rate to the accumulator
    subtract the period from the accumulator of the chosen item

下面的table显示了算法是如何进行的。这些插槽标记为 S1 到 S7。每个插槽有两列数字，每个项目的累加器值，以及对累加器的调整。

在插槽 1 中，选择了橙色，因此对累加器的调整为 +1 -7 = -6（加速率，减周期）。对于所有其他项目，调整等于比率。请注意，所有累加器都从 0 开始，并且 return 在第七个插槽之后变为 0。因此，该算法可以是运行用于任意数量的插槽，并且它会简单地重复相同的模式。

 Name    Rate  __S1__   __S2__   __S3__   __S4__   __S5__   __S6__   __S7__
Orange    1/7   0  -6   -6  +1   -5  +1   -4  +1   -3  +1   -2  +1   -1  +1   0
Banana    1/7   0  +1    1  +1    2  +1    3  -6   -3  +1   -2  +1   -1  +1   0
Apple     2/7   0  +2    2  +2    4  -5   -1  +2    1  +2    3  -5   -2  +2   0
Pineapple 3/7   0  +3    3  -4   -1  +3    2  +3    5  -4    1  +3    4  -4   0

Selected item: Orange    Pine     Apple   Banana    Pine     Apple    Pine

这是 Python 中的一个实现：

items = ['Apple', 'Apple', 'Banana', 'Pineapple', 'Pineapple', 'Pineapple', 'Orange']

# Convert the list of items into a list that contains the [name, rate, accumulator]
# for each item. The initial value for the accumulator is 0
counts = {}
for item in items:
    counts[item] = counts.get(item, 0) + 1
rates = counts.items()
rates = [[name, rate, 0] for (name, rate) in rates]
rates.sort(key=lambda x:x[1])

# Run the multiplexer, which
#    adds the item with the largest accumulator to the output
#    updates all the accumulators by adding the rate to the accumulator
#    subtracts the period from the chosen accumlator
output = []
period = len(items)
for i in range(period):
    best = 0
    for j in range(len(rates)):
        if rates[j][2] > rates[best][2]:  # compare accumulators
            best = j
        rates[j][2] += rates[j][1]        # update accumulator
    rates[best][2] -= period
    output.append(rates[best][0])         # add an item to the output

print output  # ['Orange', 'Pineapple', 'Apple', 'Banana', 'Pineapple', 'Apple', 'Pineapple']

将不同的项目均匀地放置在数组中

Place different items evenly in array

algorithm

sorting

standard-deviation

deviation