创建没有相似交叉的列表

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

我很接近。但是有些东西不起作用。也许还有更短更随机的解决方案？

在大名单中seq_CG我不希望数字连续出现。在我的示例中，它充满了许多较小的列表。然而，如果有一个 120 个数字的随机列表，每个数字均等分布，其中数字不会出现在一行中，那就更好了。

Answer 1

一个稍微天真的方法是有一个无限循环，然后用 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...

Answer 2

这里有几个解决方案。

第一个算法在序列中维护索引 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})

创建没有相似交叉的列表

Create List without similar crossovers

python

python-2.7

open-sesame