python - 保持相等值分离的排序算法

Question

心理学实验通常要求您对试验顺序进行伪随机化，这样试验显然是随机的，但您不会连续进行太多类似的试验(纯随机顺序可能会发生这种情况)。

假设每次试验的视觉显示都有颜色和尺寸:

display_list = []
colours = {0: 'red', 1: 'blue', 2: 'green', 3: 'yellow'}
sizes = [1] * 20 + [2] * 20 + [3] * 20 + [4] * 20 + [5] * 20 + [6] * 20
for i in range(120):
    display_list.append({'colour': colours[i % 4], 'size': sizes[i]})
print(display_list)

我们可以使用此函数查看任一属性具有相同值的连续试验的最大次数:

def consecutive_properties(seq, field):
    longest_run = 0
    prev_value = None
    current_run = 0
    for d in seq:
        if d[field] == prev_value:
            current_run += 1
        else:
            current_run = 1
        if current_run > longest_run:
            longest_run = current_run
        prev_value = d[field]
    return longest_run

输出:

>>> print("Consecutive colours: ", consecutive_properties(display_list, 'colour')
('Consecutive colours: ', 1)

>>> print("Consecutive sizes: ", consecutive_properties(display_list, 'size'))
('Consecutive sizes: ', 20)

您是否知道有任何算法可以最大程度地减少一个或两个属性的连续运行，或者至少将这些运行保持在指定长度以下？如果是后者，假设同一行颜色或尺寸不超过 4 个。

---

我尝试过的:

我现在的解决方案基本上有点智能bogosort ，这必须非常低效。基本上:

• 将整个列表分成包含所有属性排列的 block :如果将 display_list 分成长度为 24 的 block ，则每个 block 的每种颜色都与每种尺寸配对。假设试验列表始终可以分解为这些排列组 block ，因为您从实验设计中知道排列是什么。
• 您选择每个 block 的最大运行长度
• 你打乱每个 block ，直到每个 block 的运行长度低于最大值(这实际上意味着在整个试验列表中，你的运行长度可能是该长度的两倍，因为你可以在最后运行这个长度一个 block 和下一个 block 的开始)

Answer 1

Question: Are there any algorithms you know of that would allow minimizing the consecutive runs of either or both properties, or at least keep these runs below a specified length?

是的。有一个简单的算法可以通过简单地降低颜色或尺寸被选中的概率(如果它已经在运行中出现)来实现这一点。

from random import randrange

def choose(colors, numselections, maxrun):
    'Repeatedly choose colors.  Gradually reduce selection probability to avoid runs.'
    colors = list(colors)
    n = len(colors)
    total = n * maxrun
    current_run = 0
    for _ in range(numselections):
        i = randrange(total - current_run) // maxrun
        yield colors[i]
        colors[i], colors[-1] = colors[-1], colors[i]
        current_run = current_run + 1 if i==n-1 else 1

if __name__ == '__main__':
    colors = ['red', 'blue', 'green', 'yellow']
    for color in choose(colors, 100, maxrun=4):
        print color

请注意，与使用重选技术避免运行的其他答案相比，此方法需要更少的努力。另外，请注意运行是逐渐淡出的，而不是像其他答案中那样一次全部淡出。