Блог

Я пытаюсь создать список длиной = 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 чисел с равным распределением каждого числа, где числа не отображаются подряд.

Вот несколько решений.

Первый алгоритм поддерживает индекс 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})
  

Немного наивный подход заключается в том, чтобы иметь бесконечный цикл, затем сокращать повторяющиеся значения, используя 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...