類似のクロスオーバーのないリストを作成する

Question

私は4つの数字を含む長さ= 120のリストを作成しようとしています。 トリッキーなことは、数値が連続して表示されず、各数値が正確に同じ量で発生することです。

これは私のスクリプトです。

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

Aやや単純なアプローチは、無限ループを持つことである、そして総必要な出力をキャップする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...