1

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

一个例子是超过数百个单词，所以：

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，其他“菠萝”之间有 1 个项目偏移，并Apple放置在 [0] 和 [3] 位置。

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

4

2 回答 2

1

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

总体思路是，每个项目都有一个name、rate和accumulator，然后选择其 accumulator 中值最大的项目。在问题中给出的示例中，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

下表显示了算法的进展情况。这些插槽标记为 S1 到 S7。对于每个插槽，有两列数字，每个项目的累加器值，以及对累加器的调整。

在插槽 1 中，选择了橙色，因此对累加器的调整是+1 -7 = -6（加上利率，减去周期）。对于每个其他项目，调整等于费率。请注意，所有累加器都从 0 开始，并在第七个插槽后返回 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']
于 2020-09-02T00:39:02.420 回答
0

首先按出现次数排序您的单词。然后遍历它们，首先填充所有偶数索引，然后填充所有奇数索引。
第一个词最多可以填满所有偶数索引。在大多数现代数组中，偶数索引的槽数应至少与奇数索引的槽数一样多。如果您的语言不符合条件（即从一开始的数组），请根据可用插槽的数量选择偶数或奇数。
第二个最常见的词最多只能出现与最常见的词一样多的次数，因此以这种方式，同一个词不可能以这种方式出现在两个相邻的插槽中。
一个简单的 python 实现如下所示：

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)多次会发生什么）。它仅用于演示基本原理。

于 2020-09-01T20:09:03.883 回答