在随机列表生成中强制"没有两个相同的连续元素

Question

我有一组4个字符串，想要生成一个包含16个元素的列表，但我希望确保在这个列表中，任何两个相邻的位置都不能有相同的元素。

作为一个几乎完全是新手的Python用户，我去查看了随机库中的不同方法，发现有很多不同且有用的方法可以做类似的事情（比如random.shuffle几乎可以做到），但没有一个方法能满足我这个特定的需求。

我应该使用什么样的数据格式和方法呢？

Answer 1

这是对Zart的代码进行了修改，使其(a)能够正常工作，并且(b)提前计算了集合的减法操作：

import random

def setsub():
    # 4 strings
    sources = ['a', 'b', 'c', 'd']

    # convert them to set
    input = set(sources)
    subs = {}
    for word in sources:
        subs[word] = list(input - set([word]))

    # choose first element
    output = [random.choice(sources)]

    # append random choices excluding previous element till required length
    while len(output) < 16:
        output.append(random.choice(subs[output[-1]]))
    return output

Answer 2

如果你想要一个更通用的解决方案，可以看看Python 的生成器。

假设你有一组可以遍历的输入（比如你那四个输入字符串），下面这个生成器会从这个列表中生成一个无限的选择序列，而且相邻的两个元素不会是一样的：

import random
def noncontiguous(inputs):
  last = random.choice(inputs)
  yield last
  while True:
    next = random.choice(inputs)
    if next != last:
      last = next
      yield next

接下来，你可以使用列表推导式或者简单的 for 循环来从这个无限序列中获取16个元素的子集：

>>> gen = noncontiguous(['a', 'b', 'c', 'd'])
>>> [gen.next() for i in range(16)]
['c', 'b', 'c', 'b', 'a', 'c', 'b', 'c', 'd', 'a', 'd', 'c', 'a', 'd', 'b', 'c']

更有趣的是，你可以继续使用同一个生成器对象来创建更多不相邻的元素。

>>> for i in range(8):
...   gen.next()
...
'b'
'c'
'd'
'c'
'b'
'd'
'a'
'c'

Answer 3

伪代码算法：

1. 对每个从1到n的数字（n是你想要的元素数量）进行循环
2. 生成下一个元素
3. 如果这个元素和前一个元素相同，就再重复第2步

使用 random.choice 从一个元素列表中随机选择一个元素。

下面是一个概念验证的Python代码：

import random
sources = ['a', 'b', 'c', 'd']      # you said 4 strings
result = [random.choice(sources)]

while len(result) < 16:             # you said you need 16 elements    
    elem = random.choice(sources)
    if elem != result[-1]:
        result.append(elem)

这段代码的设计重点在于清晰易懂，而不是简洁、聪明或快速。