排序算法保持相等的值分开

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,它必须非常低效.基本上:

• 您将整个列表分成包含属性的所有排列的块:如果您分解display_list为长度为24的块,则每个块的每种颜色都与每个大小配对.让我们假设试用列表总是可以分解为这些排列块,因为您知道实验设计的排列是什么.
• 您可以选择每个块的最大运行长度
• 您将每个块移动,直到每个块的运行长度低于最大值(这实际上意味着在整个试用列表中,您的运行可能是该长度的两倍,因为您可以在一个块的末尾运行此长度和下一个的开始)

Answer 1

问题：您知道是否有任何算法可以最小化其中一个或两个属性的连续运行，或者至少将这些运行保持在指定长度以下？

是的。有一个简单的算法可以做到这一点，只需降低颜色或尺寸被选择的概率（如果它已经在运行中发生）。

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

请注意，与使用重选技术来避免运行的其他答案相比，此方法需要更少的工作。另请注意，运行是逐渐淡出的，而不是像其他答案中那样立即淡出的。