创建没有类似交叉的列表

Question

我试图建立一个长度为120的列表，其中包括4个数字。 棘手的是，数字不能出现在一行中，每个数字的出现量应该完全相同。你知道吗

这是我的剧本。你知道吗

import random
List = [1,2,3,4]
seq_CG = random.sample(List,len(List))
for i in range(121):
    randomList = random.sample(List, len(List))
    if randomList[0]!=seq_CG[-1]:
        seq_CG.append(randomList)
        i = len(seq_CG)
print List, randomList, seq_CG

我很接近。但是有些东西不起作用。也许还有一个更短更随机的解？你知道吗

在大列表中，我不希望数字排成一行。在我的例子中，它充满了许多较小的列表。不过，如果有一个120个数字的随机列表，每个数字的分布相等，而数字不是一行出现，那就更好了。你知道吗

Answer 1

这里有几个解决方案。你知道吗

第一种算法在序列中维护一个索引idx，在每次调用时idx被随机修改为不同的索引，因此生成的值不可能等于先前的值。你知道吗

from random import randrange
from itertools import islice
from collections import Counter

def non_repeating(seq):
    m = len(seq)
    idx = randrange(0, m)
    while True:
        yield seq[idx]
        idx = (idx + randrange(1, m)) % m

seq = [1, 2, 3, 4]
print(''.join(map(str, islice(non_repeating(seq), 60))))

ctr = Counter(islice(non_repeating(seq), 12000))
print(ctr)

典型输出

313231412323431321312312131413242424121414314243432414241413
Counter({1: 3017, 4: 3012, 3: 2993, 2: 2978})

该代码生成的值的分布看起来相当均匀，但我没有对其进行数学分析，我也不能保证其均匀性。你知道吗

下面的代码更复杂，但它确实提供了一个均匀分布。重复值不会被丢弃，而是临时添加到重复值池中，算法会尝试尽快使用池中的值。如果在池中找不到合适的值，它将生成一个新的随机值。你知道吗

from random import choice
from itertools import islice
from collections import Counter

def non_repeating(seq):
    pool = []
    prev = None
    while True:
        p = set(pool).difference([prev])
        if p:
            current = p.pop()
            pool.remove(current)
        else:
            current = choice(seq)
            if current == prev:
                pool.append(current)
                continue
        yield current
        prev = current

seq = [1, 2, 3, 4]
print(''.join(map(str, islice(non_repeating(seq), 60))))

ctr = Counter(islice(non_repeating(seq), 12000))
print(ctr)

典型输出

142134314121212124343242324143123212323414131323434212124232
Counter({4: 3015, 2: 3005, 3: 3001, 1: 2979})

如果输入序列的长度只有2或3，则池可能会变得相当大，但对于较长的序列，它通常只保存几个值。你知道吗

---

最后，这里给出了一个精确的均匀分布。不要试图在包含2个（或更少）元素的输入序列上使用它，因为它很可能陷入无限循环；当然，对于这样的输入序列，无论如何只有2种解决方案。：）

我并不为这段相当难看的代码感到骄傲，但至少它确实起到了作用。我正在创建一个长度为60的输出列表，这样就可以很好地显示在屏幕上，但是这段代码在生成更大的序列时没有问题。你知道吗

from random import shuffle
from itertools import groupby
from collections import Counter

def non_repeating(seq, copies=3):
    seq = seq * copies
    while True:
        shuffle(seq)
        result, pool = [], []
        for k, g in groupby(seq):
            result.append(k)
            n = len(list(g)) - 1
            if n:
                pool.extend(n * [k])

        for u in pool:
            for i in range(len(result) - 1):
                if result[i] != u != result[i + 1]:
                    result.insert(i+1, u)
                    break
            else:
                break
        else:
            return result

# Test that sequence doesn't contain repeats
def verify(seq):
    return all(len(list(g)) == 1 for _, g in groupby(seq))

seq = [1, 2, 3, 4]
result = non_repeating(seq, 15)
print(''.join(map(str, result)))
print(verify(result))
print(Counter(result))

典型输出

241413414241343212423232123241234123124342342141313414132313
True
Counter({1: 15, 2: 15, 3: 15, 4: 15})

Answer 2

一种稍微简单的方法是使用无限循环，然后使用islice来限制所需的总输出，例如：

from itertools import groupby
from random import choice

def non_repeating(values):
    if not len(values) > 1:
        raise ValueError('must have more than 1 value')
    candidates = iter(lambda: choice(values), object())
    # Python 3.x   yield from (k for k, g in groupby(candidates))
    # Python 2.x
    for k, g in groupby(candidates):
        yield k

data = [1, 2, 3, 4]
sequence = list(islice(non_repeating(data), 20))
# [3, 2, 1, 4, 1, 4, 1, 4, 2, 1, 2, 1, 4, 1, 4, 3, 2, 3, 4, 3]
# [3, 2, 3, 4, 1, 3, 1, 4, 1, 4, 2, 1, 2, 3, 2, 4, 1, 4, 2, 3]
# etc...