셔플 목록

Question

나는 다음과 같은 목록을 가지고 :

a=['airplane','track','car','train'] 

나는 두 번이 목록의 모든 항목을 표시하는 목록을 작성 좋아하지만, 다음 두 행에 대한 항목의 반복을 방지 할 것 .

b=['airplane','track','car','airplane','train','track','car' etc.] 

하지만 C는 않을 것 :

c=['airplane,'track','airplane', etc.] 

나는 어떤 종류의 생각 즉 비행기는 한 비행기 후 나타날 수있는 2 개 개의 다른 항목 사이에있는 정도로, b는 좋은 후보가 될 것입니다 의미 1. 아마 뭔가 아래와 같이 (반복에 대한 2 random.shuffle (가) 3. 테스트를 중복 :

curWord[n]==curWord[n+1] 

bruteforce 작업

4. TRUE 인 경우 다시 섞어서 다시 시작하십시오. (실제로 명령이 파이썬에게 진리 값을 읽도록 지시하는 것이 무엇인지 알지 못합니다. if 문이 작동한다고 상상하지만, FALSE의 경우에는 파이썬이 계속 수행하도록 지시하는 방법을 모르겠습니다. 어떤 경우

, 위의 내 자신의 지식에 대한 좋은 것 특정 질문에 대한 답변을 받고 있지만, 나는 생각했다 구현 아마 목록이 증가함에 따라 정말 오래 걸릴 것이라고 볼 수 있습니다.

하나를 제안 사항?

도움을 주셔서 감사합니다.

Answer 1

각 요소의 사본이 두 개인 목록이 필요한 경우 원본 목록이 2 개보다 길면이 기능이 작동하지 않는 이유가 있습니까?

In [138]: a=['airplane','track','car','train'] 

In [139]: a + a 
Out[139]: ['airplane', 'track', 'car', 'train', 'airplane', 'track', 'car', 'train'] 

당신은 다음을 "어떻게 그들이 동일한 요소의 두 가지 요소 내에서 표시되지 않습니다 있도록 내 목록 요소의 순열의 공간에서 샘플 않는다"의보다 추상적 인 질문을하는 경우해야 작업.

는 요소가 두 번 표시 어떤 구조를 점점 a + a만큼 쉽게 한 다음 a + a의 순열을 제한하지 걱정할 수

주 - overthink 할 필요는 문제의 일부 "내가 어떻게 각각의 두받을 수 있나요" . 그런 다음이로 사용할 수 있습니다

import random 

def valid_duplicate_spacing(x): 
    for i, elem in enumerate(x): 
     if elem in x[i+1:i+3]: 
      return False 
    return True 

def sample_permutations_with_duplicate_spacing(seq): 
    sample_seq = seq + seq     
    random.shuffle(sample_seq)  
    while not valid_duplicate_spacing(sample_seq): 
     random.shuffle(sample_seq) 

    return sample_seq 

은 다음과 같습니다

In [165]: sample_permutations_with_duplicate_spacing(a) 
Out[165]: ['airplane', 'train', 'track', 'car', 'train', 'track', 'car', 'airplane'] 

In [166]: sample_permutations_with_duplicate_spacing(a) 
Out[166]: ['train', 'airplane', 'car', 'track', 'train', 'airplane', 'track', 'car'] 

당신은 단순히 무작위로 두 사람은 다음에 대한 샘플, 당신은 할 수립니다 대체되지 않도록, 목록에서 샘플링에 대해 이야기하는 경우

In [146]: foo = draw_with_delayed_replacement(a) 

In [147]: foo.next() 
Out[147]: 'car' 

In [148]: foo.next() 
Out[148]: 'train' 

In [149]: foo.next() 
Out[149]: 'track' 

In [150]: foo.next() 
Out[150]: 'car' 

In [151]: foo.next() 
Out[151]: 'train' 

In [152]: foo.next() 
Out[152]: 'track' 

In [153]: foo.next() 
Out[153]: 'car' 

In [154]: foo.next() 
Out[154]: 'airplane' 

In [155]: foo.next() 
Out[155]: 'track' 

In [156]: foo.next() 
Out[156]: 'train' 

:

import random 

def draw_with_delayed_replacement(seq): 
    drawn = random.choice(seq) 
    rejectables = [drawn] 
    yield drawn 

    drawn = random.choice(seq) 
    while drawn in rejectables: 
     drawn = random.choice(seq) 
    rejectables.append(drawn) 
    yield drawn 

    while True: 
     drawn = random.choice(seq) 
     if drawn in rejectables: 
      continue 
     else: 
      rejectables.pop(0) 
      rejectables.append(drawn) 
      yield drawn 

그런 다음 다음과 같은 작업을 수행 할 수 있습니다 발전기를 사용

그러나이 경우 각 요소가 정확히 두 번 나타나는 샘플을 얻을 수 있다고 보장 할 수는 없으며 작은 목록에서는 비효율적 일 수 있습니다.

Answer 2

여기 내 해결책이 있습니다. 그렇다고해서 모든 토큰이 정확히 n 번 나타납니다.

내 솔루션을 쉽게 확장하여이를 보장 할 수는 있지만 그럴 경우 확인해야 할 교착 상태가 발생할 수 있습니다.

>>> def magicsequence(tokens, length): 
... sequence = [] 
... while len(sequence) < length: 
...  candidate = random.choice(tokens) 
...  if candidate not in sequence[-2:]: 
...  sequence.append(candidate) 
... return sequence 

Answer 3

다음은 제약 조건을 충족시키고 항상 각 요소가 두 번있는 목록을 반환하는 솔루션입니다. 그것은 O (n^2) 시간에 실행됩니다. 여기서 n은 목록의 길이입니다.

from collections import Counter 
from itertools import permutations 
from random import choice, shuffle 

def shuffle_with_constraints(x): 
    if len(x) < 3: 
     raise ValueError("Lists with length less than 3 have no valid shuffles") 

    output = [] 
    #a counter representing how many times we still need to insert an element 
    available = Counter(x*2) 
    while available: 

     if len(output) == len(x)*2-6: #we just need to insert six elements 
      distinct = len(available) #how many distinct elements we need to insert 

      if distinct == 6: 
       pass #there is no problem 
      elif distinct == 3: #only six possibilities 
       end = list(available) 
       shuffle(end) 
       return output + end*2 
      else: 
       #enumerate all 720 permutations and select a valid one 
       possibles = [possible for possible in permutations(available.elements()) 
          if valid_6_shuffle(possible)] 
       return output+list(choice(possibles)) 

     #choose a valid element and append it to the output 
     next = choice(list(set(available)-set(output[-2:]))) 
     output.append(next) 

     #remove it from the availables 
     if available[next] == 2: 
      available[next] -= 1 
     else: 
      del available[next] 

    return output 

def valid_6_shuffle(x): 
    for a,b,c in zip(x,x[1:],x[2:]): 
     if a==b or b==c or a==c: 
      return False 

    return True