Применение "нет 2 одинаковых смежных элементов" в генерации случайного списка - PullRequest
Новая
       16

Применение "нет 2 одинаковых смежных элементов" в генерации случайного списка

2 голосов
/ 11 июля 2011

У меня есть набор из 4 строк, и я хочу создать список из 16 элементов, но с применением правила (или получая тот же результат, что и применение такого правила), чтобы никогда не повторять один и тот же элемент в двух смежных позициях в результирующем список.

Будучи почти новичком в Python, я пошел проверять различные методы в случайной библиотеке и нашел много разных и полезных способов сделать что-то похожее (random.shuffle почти сработал бы), но никто из них не занимался этим моя особая потребность.

Какой формат данных и какие методы мне следует использовать?

Ответы [ 5 ]

6 голосов
/ 11 июля 2011

алгоритм псевдокода:

  1. Для i в n (n - количество элементов, которое вы хотите)
  2. Создать следующий элемент
  3. Если он такой же, как предыдущий элемент, повторите 2

Используйте random.choice, чтобы случайным образом выбрать элемент из списка элементов.

Вот подтверждение концепции кода Python: 

import random
sources = ['a', 'b', 'c', 'd']      # you said 4 strings
result = [random.choice(sources)]

while len(result) < 16:             # you said you need 16 elements    
    elem = random.choice(sources)
    if elem != result[-1]:
        result.append(elem)

Этот код оптимизирован для ясности, а не краткости, хитрости или скорости.

3 голосов
/ 11 июля 2011

Для более общего решения вы можете обратиться к Генераторам Python .

При произвольной повторяемости входных данных (например, ваших четырех входных строк) следующий генератор будет генерировать бесконечноеитерируемый выбор из этого списка, без двух одинаковых элементов: 

import random
def noncontiguous(inputs):
  last = random.choice(inputs)
  yield last
  while True:
    next = random.choice(inputs)
    if next != last:
      last = next
      yield next

Затем вы можете использовать списки или базовый цикл for, чтобы получить подмножество из 16 элементов этой бесконечной последовательности: 

>>> gen = noncontiguous(['a', 'b', 'c', 'd'])
>>> [gen.next() for i in range(16)]
['c', 'b', 'c', 'b', 'a', 'c', 'b', 'c', 'd', 'a', 'd', 'c', 'a', 'd', 'b', 'c']

Что еще интереснее, вы можете продолжать использовать один и тот же объект-генератор для создания нескольких несмежных элементов 

>>> for i in range(8):
...   gen.next()
...
'b'
'c'
'd'
'c'
'b'
'd'
'a'
'c'
2 голосов
/ 11 июля 2011

Код Зарта, модифицированный для (а) работы и (б) предварительного вычисления установленных вычитаний: 

import random

def setsub():
    # 4 strings
    sources = ['a', 'b', 'c', 'd']

    # convert them to set
    input = set(sources)
    subs = {}
    for word in sources:
        subs[word] = list(input - set([word]))

    # choose first element
    output = [random.choice(sources)]

    # append random choices excluding previous element till required length
    while len(output) < 16:
        output.append(random.choice(subs[output[-1]]))
    return output
1 голос
/ 11 июля 2011

Это пересмотренная версия Eli, в которой нет элементов грубой силы и, надеюсь, не хватает ясности: 

import random

# 4 strings
sources = ['a', 'b', 'c', 'd']

# convert them to set
input = set(sources)

# choose first element
output = [random.choice(input)]

# append random choices excluding previous element till required length
while len(output) < 16:
    output.append(random.choice(input - set(output[-1:])))
1 голос
/ 11 июля 2011

Довольно серьезное злоупотребление itertools: 

import itertools
import random

print list(itertools.islice((x[0] for x in
  itertools.groupby(random.randint(1, 10) for y in itertools.count())), 16))

Он использует islice(), чтобы получить первые 16 элементов бесконечного генератора, основанного на count(), используя groupby(), чтобы свернуть равные соседние элементы.

...