带有重复约束的列表洗牌 2-back python

Question

我有一个这样的列表：

a=['airplane','track','car','train']

我想创建一个新的列表，让这个列表里的每个项目都出现两次，但要确保在接下来的两行中不会重复出现同样的项目。也就是说，像“飞机”这种项目只能在中间有两个不同的项目后才能再次出现，所以“b”是一个不错的选择：

b=['airplane','track','car','airplane','train','track','car' etc.]

但“c”就不行：

c=['airplane,'track','airplane', etc.]

我在想一种暴力破解的方法，步骤如下：

1. 先把“a”复制一份
2. 然后随机打乱这个“a”
3. 接着检查是否有重复（可能像下面这样）：

curWord[n]==curWord[n+1]

4. 如果有重复，就重新打乱并从头开始。我其实不知道用什么命令让Python来判断真假值。我想用一个if语句应该可以，但如果是FALSE的话，我就不知道该怎么让Python继续进行下去。

总之，虽然能解答我上面提到的具体问题对我自己的学习有帮助，但我觉得我考虑的这个方法在列表变大时可能会非常耗时。

有什么建议吗？

提前谢谢你的帮助！

Answer 1

这里有一个解决方案，它满足所有的条件，并且总是返回一个列表，里面的每个元素都出现两次。这个方法的运行时间是O(n^2)，其中n是列表的长度。

from collections import Counter
from itertools import permutations
from random import choice, shuffle

def shuffle_with_constraints(x):
    if len(x) < 3:
        raise ValueError("Lists with length less than 3 have no valid shuffles")

    output = []
    #a counter representing how many times we still need to insert an element
    available = Counter(x*2)
    while available:

        if len(output) == len(x)*2-6: #we just need to insert six elements
            distinct = len(available) #how many distinct elements we need to insert

            if distinct == 6:
                pass #there is no problem
            elif distinct == 3: #only six possibilities
                end = list(available)
                shuffle(end)
                return output + end*2
            else:
                #enumerate all 720 permutations and select a valid one
                possibles = [possible for possible in permutations(available.elements())
                             if valid_6_shuffle(possible)]
                return output+list(choice(possibles))

        #choose a valid element and append it to the output
        next = choice(list(set(available)-set(output[-2:])))
        output.append(next)

        #remove it from the availables
        if available[next] == 2:
            available[next] -= 1
        else:
            del available[next]

    return output

def valid_6_shuffle(x):
    for a,b,c in zip(x,x[1:],x[2:]):
        if a==b or b==c or a==c:
            return False

    return True

Answer 2

这是我的解决方案，不过它并不能保证每个标记（token）都出现恰好 n 次。

其实可以很简单地扩展我的方案来保证这一点，但那样可能会导致一种叫做死锁的情况，这种情况需要额外检查。

>>> def magicsequence(tokens, length):
...   sequence = []
...   while len(sequence) < length:
...     candidate = random.choice(tokens)
...     if candidate not in sequence[-2:]:
...        sequence.append(candidate)
...   return sequence

Answer 3

如果你只是想要一个列表，其中每个元素都有两个副本，那么当原始列表的元素超过两个时，这种方法有什么问题吗？

In [138]: a=['airplane','track','car','train']

In [139]: a + a
Out[139]: ['airplane', 'track', 'car', 'train', 'airplane', 'track', 'car', 'train']

如果你问的是一个更抽象的问题：“我该如何从我的列表元素的排列中抽样，以确保相同的元素不会在两个元素之内出现？”那么下面的方法应该可以解决这个问题。

需要注意的是，想要让元素出现两次其实很简单，只需要用 a + a 这样的方式，然后你可以再考虑如何限制 a + a 的排列方式——不需要过于纠结“我该如何得到每个元素两个副本”这个部分。

import random

def valid_duplicate_spacing(x):
    for i, elem in enumerate(x):
        if elem in x[i+1:i+3]:
            return False
    return True

def sample_permutations_with_duplicate_spacing(seq):
    sample_seq = seq + seq                 
    random.shuffle(sample_seq)    
    while not valid_duplicate_spacing(sample_seq):
        random.shuffle(sample_seq)

    return sample_seq

然后可以这样使用：

In [165]: sample_permutations_with_duplicate_spacing(a)
Out[165]: ['airplane', 'train', 'track', 'car', 'train', 'track', 'car', 'airplane']

In [166]: sample_permutations_with_duplicate_spacing(a)
Out[166]: ['train', 'airplane', 'car', 'track', 'train', 'airplane', 'track', 'car']

如果你只是想随机从列表中抽样，确保在接下来的两个抽样中不会重复使用同一个样本，你可以使用生成器：

import random 

def draw_with_delayed_replacement(seq):
    drawn = random.choice(seq)
    rejectables = [drawn]
    yield drawn

    drawn = random.choice(seq)
    while drawn in rejectables:
        drawn = random.choice(seq)
    rejectables.append(drawn)
    yield drawn

    while True:
        drawn = random.choice(seq)
        if drawn in rejectables:
            continue
        else:
            rejectables.pop(0)
            rejectables.append(drawn)
            yield drawn

然后你可以这样做：

In [146]: foo = draw_with_delayed_replacement(a)

In [147]: foo.next()
Out[147]: 'car'

In [148]: foo.next()
Out[148]: 'train'

In [149]: foo.next()
Out[149]: 'track'

In [150]: foo.next()
Out[150]: 'car'

In [151]: foo.next()
Out[151]: 'train'

In [152]: foo.next()
Out[152]: 'track'

In [153]: foo.next()
Out[153]: 'car'

In [154]: foo.next()
Out[154]: 'airplane'

In [155]: foo.next()
Out[155]: 'track'

In [156]: foo.next()
Out[156]: 'train'

不过，在这种情况下，你不能保证每个元素都会出现恰好两次，而且对于小列表来说，这种方法可能效率不高。