带有重复约束2-back python的shuffle list

I have the following list:

我有以下列表:

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

I would like to create a list that presents every item of this list twice, but prevents item repetitions for the next two rows. That means airplane can only appear after airplane as long as 2 different items are in between so b would be a good candidate:

我想创建一个列表,列出两次此列表的每个项目,但阻止下两行的项目重复。这意味着飞机只能在飞机上出现,只要介于两个不同的项目之间,所以b将是一个很好的候选人:

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

but c would not:

但是c不会:

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

I was thinking of some kind of bruteforce operation where: 1. a is duplicated 2. random.shuffle(a) 3. test for repetition (maybe something like below:

我正在考虑某种强力操作,其中:1。a重复2. random.shuffle(a)3。重复测试(可能如下所示:

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

4. Re-shuffle if TRUE and start over. (I don't actually know what the command would be to instruct python to read the truth value. I imagine an if statement will work, but in the case of a FALSE I don't know how I'd instruct python to carry on

如果为TRUE则重新洗牌并重新开始。 (我实际上并不知道命令是什么命令python读取真值。我想if语句会起作用,但是如果是FALSE我不知道如何指示python继续

In any case, although getting answers to the particular questions above would be good for my own knowledge, I can see that the implementation I have considered would probably take really long as the list increases.

在任何情况下,虽然获得上述特定问题的答案对我自己的知识有好处,但我可以看到,我所考虑的实现可能需要很长时间,因为列表增加了。

Any suggestions?

Thanks in advance for your help!

在此先感谢您的帮助!

3 个解决方案

#1

If you just need some list with two copies of each element, is there a reason why this won't work for when the original list is longer than 2 elements?

如果你只需要一个包含每个元素的两个副本的列表,那么当原始列表超过2个元素时,这是不是有效的原因?

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

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

If you are asking the more abstract question of, "How do I sample from the space of permutations of my list elements such that they don't appear within two elements of an identical element" then the following should work.

如果你问的是更抽象的问题,“如何从列表元素的排列空间中采样,使它们不出现在同一元素的两个元素中”,那么以下内容应该有效。

Note that getting some structure where the elements appear twice is as easy as a + a and then you can worry about restricting the permutations of a + a -- no need to overthink the "how do I get two of each" part of the problem.

注意,获得一些元素出现两次的结构就像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

Then this can be used as follows:

然后这可以使用如下:

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']

If you're talking about merely randomly sampling from the list, such that a sample is not replaced for the two following draws, you could use a generator:

如果您只是在谈论从列表中随机抽样,以便在下面两次抽奖中不替换样本,您可以使用生成器:

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

Then you can do the following:

然后你可以做以下事情:

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'

However, in this case you can't guarantee you're going to get a sample where each element appears exactly twice, and this may be inefficient for small lists.

但是,在这种情况下,您不能保证您将获得每个元素恰好出现两次的样本,这对于小型列表来说可能效率低下。

#2

Here is my solution, which does not guarantee that every token appears exactly n times, though.

这是我的解决方案,但并不能保证每个令牌只出现n次。

One could easily extend my solution to guarantee that, but that would result in a possible deadlock scenario which one would have to check for then.

人们可以轻松地扩展我的解决方案以保证这一点,但这会导致可能出现的死锁情况,然后必须检查。

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

#3

Here is a solution that satisfies the constraints and always returns a list with each element twice. It runs in O(n^2) time, where n is the length of the list.

这是一个满足约束的解决方案,并始终返回每个元素两次的列表。它在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