Создать список без аналогичных кроссоверов

Question

Я пытаюсь построить список length = 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

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

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