Генерация конкретных шаблонов перестановок в Python - PullRequest
Новая
       79

Генерация конкретных шаблонов перестановок в Python

0 голосов
/ 07 декабря 2018

Я пытаюсь смоделировать вероятностную систему.Система, с которой я работаю, включает три элемента - назовите их «X», «Y» и «Z».Эти элементы образуют строки в определенном типе чередующегося шаблона, где X должен чередоваться с Y или Z (т. Е. Соединения XX, YY, ZZ, YZ и ZY запрещены).Я хотел бы переставить списки всех возможных последовательностей для различных длин строк.

Моя первоначальная попытка состояла в том, чтобы сгенерировать все возможные перестановки этих трех символов и отфильтровать любые запрещенные шаблоны.К сожалению, перестановки очень плохо масштабируются для длинных последовательностей.Я решил эту проблему, генерируя каждую последовательность, по одному символу за раз, и проверяя условия, которые я излагал при создании последовательности.Это предотвращает генерацию непродуктивных последовательностей очень рано и резко уменьшает количество генерируемых перестановок.Проблема в том, что я не очень много программист, и мне пришлось жестко закодировать несколько вложенных циклов for, чтобы достичь этой цели.Код ниже показан для длины строки 5. 

Length = 5
Units = ['X','Y','Z']
Sequences = []

#aij is the j'th character in the sequence

for i1 in range(len(Units)):
    ai1 = n[i1]
    for i2 in range(len(Units)):
        ai2 = Units[i2]

#If the two most recent sequential units are identical OR (Y and Z) OR (Z and Y), pass

    if ai2 == ai1 or ai2==Units[1] and ai1==Units[2] or ai2==Units[2] and ai1==Units[1]:
        pass
    else:

#repeat for the other characters in the sequence until the final character is reached

        for i3 in range(len(Units)):
            ai3 = Units[i3]
            if ai3 == ai2 or ai3==Units[1] and ai2==Units[2] or ai3==Units[2] and ai2==Units[1]:
                pass
            else:
                for i4 in range(len(Units)):
                    ai4 = Units[i4]
                    if ai4 == ai3 or ai4==Units[1] and ai3==Units[2] or ai4==Units[2] and ai3==Units[1]:
                        pass
                    else:
                        for i5 in range(len(Units)):
                            ai5 = Units[i5]
                            if ai5 == ai4 or ai5==Units[1] and ai4==Units[2] or ai5==Units[2] and ai4==Units[1]:
                                pass
                            else:

#Append the valid sequence to my list of Sequences

                                a = ai1 + ai2 + ai3 + ai4 + ai5
                                Sequences.append(a)

print(Sequences)

Вывод: 

['XYXYX', 'XYXZX', 'XZXYX', 'XZXZX', 'YXYXY', 'YXYXZ', 'YXZXY', 'YXZXZ', 'ZXYXY', 'ZXYXZ', 'ZXZXY', 'ZXZXZ']

Мой вопрос: как я могу обобщить этот тип алгоритма для функциичто просто принимает входной "Длина" (т.е. количество символов в строке) и генерирует все мои шаблоны последовательности в списке?

Ответы [ 2 ]

0 голосов
/ 08 декабря 2018

Для ['X','Y','Z'] существует 9 пар, которые можно создать.Но пара XX, YY, ZZ, YZ, ZY запрещена.Так и осталось XY,XZ,YX,ZX.Разделите его на две единицы (units1 и units2), чтобы избежать перестановки XX.Если length является четным, он просто выполняет перестановку для каждой единицы, используя продукт itertools (см .: генерация перестановок с повторениями в python ).Он выдаст список кортежей, которые можно соединить со строкой (см .: Почему я не могу присоединиться к этому кортежу в Python? ).Добавьте к этому списку два.

В нечетном случае комбинации единиц 1 приведут к любой комбинации с префиксом X, поэтому добавьте 'X' к последней из каждой строки и Y,Z к началу.Для юнитов 2 комбинации делайте наоборот.Он выдаст не уникальный список, поэтому приведение к set только для того, чтобы сделать его уникальным 

import itertools

def combine(length):
    units1 = ['XY','XZ']
    units2 = ['YX','ZX']

    combine1 = ["".join(map(str,p)) for p in itertools.product(units1,repeat=int(length/2))]
    combine2 = ["".join(map(str,p)) for p in itertools.product(units2,repeat=int(length/2))]

    if (length%2 == 1):
        combine1_odd = [item + 'X' for item in combine1] + ['Y' + item for item in combine1] + ['Z' + item for item in combine1]
        combine2_odd = ['X' + item for item in combine2] + [item + 'Y' for item in combine2] + [item + 'Z' for item in combine2]
        return list(set(combine1_odd + combine2_odd))

    return list(set(combine1 + combine2))

print(combine(5))
0 голосов
/ 07 декабря 2018

Вы можете использовать генератор с рекурсией: 

def combinations(d, _len, current = []):
  if len(current) == _len:
     yield current
  else:
     for i in d:
       if not current or ('X' in current and current[-1] != i):
         yield from combinations(d, _len, current+[i])


results = list(map(''.join, combinations(['X','Y','Z'], 5)))
final_results = [a for i, a in enumerate(results) if a not in results[:i]]

Выход: 

['XYXYX', 'XYXYZ', 'XYXZX', 'XYXZY', 'XYZXY', 'XYZXZ', 'XYZYX', 'XYZYZ', 'XZXYX', 'XZXYZ', 'XZXZX', 'XZXZY', 'XZYXY', 'XZYXZ', 'XZYZX', 'XZYZY']
...