Фильтрация перестановок itertools по длине полученного питона перестановки - PullRequest
Новая
       14

Фильтрация перестановок itertools по длине полученного питона перестановки

0 голосов
/ 28 июня 2018

Привет, у меня совершенно нет идей.

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

items = ["q", "q.", "qg", "q.g.", "q.g", "qgr", "q.g.r", "q.g.r.", "qghr", "q.g.h.r", "q.g.h.r.", "q.g.r.h", "q.g.r.h.", "qakky", "qakky.", "qak", "qak.", "qkgr", "q.k.g.r", "q.k.g.r.", "qkghr", "q.k.gh.r", "q.k.gh.r.", "qr", "q.r.", "q.r", "gokoaheo", "gokoaheo.", "goko", "goko.", "g", "g.", "r", "r.", "rhk.", "k.", "k", "rhk", "gho", "ghr", "gr", "kgr", ".", ".", "goh", "goho", "gho.", "goho.", "rohok", "rohok.", "roh", "roh.", "kat.", "q", "q.", "qgr", "qghr"]

Каждая результирующая перестановка должна быть следующей :

  1. Начните с 'q'
  2. Не может заканчиваться на '.'
  3. Не должно иметь ни одной из следующих подстрок: '..', 'ee', 'oo', 'll', 'gg', 'aa'
  4. Должно иметь не более 2 'q's' r's и 'g's; Не более 4-х часов; не более 5 'k или'.
  5. Не может содержать более 13 символов или менее 9.

Поэтому я написал следующую функцию для просеивания каждой перестановки: 

def badseq(item):

    patt=re.compile('\.$|^[^q]')

    lets = ['q','g','r','h','o','k','.','..','gg','oo','ll','aa','ee']
    nums = [2,2,2,4,4,5,0,0,0,0,0,0]
    if len(item) > 13 or len(item) < 9:
        return True
    for i in range(len(lets)):
        l=lets[i]
        n=nums[i]
        if item.count(l) > n :
            return True
        elif re.search(patt, item):
            return True
    return False

Есть ли лучший способ сделать это, чем вычислить так много перестановок, а затем отфильтровать их одну за другой? 

completelist=[]
for repetitions in range(8):
    perms=["".join(x) for x in itertools.permutations(items, repetitions) if not badseq("".join(x))]
    completelist.extend(perms)
    completelist=[x for x in set(completelist)]

Проблема в том, что, поскольку я не возражаю против того, сколько существует повторений и все подстроки разной длины, я не знаю, сколько повторений нужно использовать в аргументе itertools. Я пошел с 8, потому что есть ряд подстрок из одного или двух символов, но я могу вычислить много дубликатов. Или я могу совершенно неправильно понять, что я здесь делаю:)

Я был бы очень признателен за любые идеи относительно способа быстрой фильтрации перестановок, чтобы было меньше генерации; или способ выяснить, сколько повторений мне нужно, чтобы покрыть все из них. Я могу опубликовать свой полный код многопроцессорной обработки, но решил, что постараюсь сохранить его в точном соответствии с рекомендациями SO для новичков (это всего лишь pool.starmap повторений и список функций, в основном как указано выше.

...