11

心理学实验通常要求您对试验顺序进行伪随机化，这样试验显然是随机的，但您不会连续获得太多类似的试验（这可能发生在纯随机排序中）。

假设每次试验的视觉显示都有颜色和大小：

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 的块，则每个块的每种颜色都与每种大小配对。让我们假设试验列表总是可以分解成这些排列块，因为您从实验设计中知道排列是什么。
  • 您选择每个块的最大运行长度
  • 你打乱每个块，直到每个块的运行长度低于最大值（这实际上意味着在整个试验列表中，你的运行可能是那个长度的两倍，因为你可以在一个块的末尾运行这个长度和下一个的开始）
4

5 回答 5

3

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

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

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

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

于 2013-05-27T09:10:39.467 回答
1

正如ddyer所说，您对随机性而不是排序感兴趣。我的解决方案是：

  1. 从源列表中选择一个随机 A 元素
  2. 从您的目的地列表中选择一个随机位置 I
  3. 在位置 I 处插入 A 到 dest。列表
  4. 检查目的地列表是否有效。如果不是，则恢复之前的状态并重复

一个工作片段：

from random import randint
from operator import itemgetter
from itertools import islice

def reshuffle(_items, max_consequent):
    items = _items[:]
    new_order = []
    while items:
        src_pos = randint(0, len(items)-1)
        dest_pos = randint(0, len(new_order))
        item = items[src_pos]
        new_order.insert(dest_pos, item)
        if is_new_order_fine(new_order, max_consequent):
            items.pop(src_pos)
        else:
            new_order.pop(dest_pos)
    return new_order

def is_new_order_fine(items, n_max):
    return (
        not has_consecutive_keys(items, n_max, key=itemgetter('colour')) and
        not has_consecutive_keys(items, n_max, key=itemgetter('size')))

# can be optimised - don't check all items, just surrounding N
def has_consecutive_keys(items, n_max, key):
    _has_n_keys = False
    if len(items) >= n_max:
        last_value = key(items[0])
        n_consequent = 1
        for item in items[1:]: # can optimize by using iterator
            if key(item) == last_value:
                n_consequent += 1
            else:
                last_value = key(item) 
                n_consequent = 1
            if n_consequent >= n_max:
                _has_n_keys = True
                break
    return _has_n_keys

请注意，您不需要每次都检查目标列表中的所有项目，插入的新项目左右两侧的K（未在代码段中实现）

编辑：

  • 您可以使用groupby in has_consecutive_keys（但不排序！）
于 2013-05-27T06:10:16.853 回答
1

你显然不关心真正的随机性，所以如果你定义一个距离度量，并随机绘制你的序列，你可以拒绝任何新的绘制，如果它的距离与前一次绘制“太接近”，然后再次绘制。

如果你从一个有限的集合（比如一副牌）中抽牌，那么整个牌组可以是牌堆，你的排序将包括在找到接近的对时交换两个元素，但如果出现以下情况，也会拒绝交换伙伴交换的元素将变得不可接受，因此每个交换步骤都会使整个集合得到改进。

如果您的标准不太难满足，这将很快终止。

于 2013-05-27T05:52:57.733 回答
1

如果连续元素的可能性不是很高（如您的示例），如果不满足条件，我会简单地重新洗牌。如您所见，大多数时候您只需一次尝试就可以成功，因此非常有效。

In [1]: from random import shuffle

In [2]: from itertools import groupby

In [3]: from collections import Counter

In [4]: def pseudo_shuffle(lst, limit, tries=1):
   ...:     temp = list(lst)
   ...:     shuffle(temp)
   ...:     if max(sum(1 for x in g) for k, g in groupby(temp)) <= limit:
   ...:         return tries #return temp
   ...:     return pseudo_shuffle(lst, limit, tries=tries+1)

In [5]: colors = 30*['red', 'blue', 'green', 'yellow']

In [6]: sizes = [1] * 20 + [2] * 20 + [3] * 20 + [4] * 20 + [5] * 20 + [6] * 20

In [7]: Counter([pseudo_shuffle(colors, 4) for _ in range(1000)])
Out[7]: Counter({1: 751, 2: 200, 3: 38, 4: 10, 5: 1})

In [8]: Counter([pseudo_shuffle(sizes, 4) for _ in range(1000)])
Out[8]: Counter({1: 954, 2: 44, 3: 2})
于 2013-05-27T06:30:19.760 回答
0

抱歉，这不是答案，但很难在评论中发布代码。这是编写consecutive_properties函数的一种更简单的方法

from operator import itemgetter
from itertools import groupby
def consecutive_properties(seq, field):
    return max(sum(1 for x in g) for k,g in groupby(seq, key=itemgetter(field)))

当我正确理解您的问题时，我会尝试将其变成答案:)

于 2013-05-27T05:32:00.213 回答