Быстрый способ генерации комбинаций с ограничениями?

Question

У меня есть функция генератора, которая создает декартово произведение списков. Реальное приложение использует более сложные объекты, но они могут быть представлены строками:

import itertools 

s1 = ['a', 'b'] 
s2 = ['c', 'd', 'e', 'f'] 
s3 = ['c', 'd', 'e', 'f'] 
s4 = ['g'] 

p = itertools.product(*[s1,s2,s3,s4]) 
names = [''.join(s) for s in p] 

В этом примере, в результате 32 комбинаций символов:

names 
['accg', 'acdg', 'aceg', 'acfg', 'adcg', 'addg', 'adeg', 'adfg', 'aecg', 
'aedg', 'aeeg', 'aefg', 'afcg', 'afdg', 'afeg', 'affg', 'bccg', 'bcdg', 
'bceg', 'bcfg', 'bdcg', 'bddg', 'bdeg', 'bdfg', 'becg', 'bedg', 'beeg', 
'befg', 'bfcg', 'bfdg', 'bfeg', 'bffg'] 

Теперь, скажем, у меня есть некоторые ограничения так что некоторые комбинации символов являются незаконными. Например, допустим, что допустимы только строки, содержащие регулярное выражение '[ab] .c'. («А» или «б» с последующим любой буквой с последующим «с»)

После применения этих ограничений, мы остались с сокращенным набором всего 8 строк:

import re 
r = re.compile('[ab].c') 
filter(r.match, names) 
['accg', 'adcg', 'aecg', 'afcg', 'bccg', 'bdcg', 'becg', 'bfcg'] 

В реальном приложении цепи длиннее, могут быть тысячи комбинаций и применение сотен ограничений достаточно интенсивно вычислительно, поэтому я заинтересован в масштабируемости.

Сейчас я просматриваю каждую комбинацию и проверяю ее достоверность. Существует ли алгоритм/структура данных, способный ускорить этот процесс?

EDIT: Может быть, это прояснит немного: В реальном приложении я собираю случайные 2D фотографии зданий из простых базовых блоков (например, столбы, сегменты крыши, окна и т.д.). Ограничения ограничивают, какие блоки (и их вращения) могут быть сгруппированы вместе, поэтому полученное случайное изображение выглядит реалистичным, а не случайным беспорядком.

Данное ограничение может содержать множество комбинаций шаблонов. Но из всех этих комбинаций многие из них недействительны, потому что другое ограничение может запретить часть его. Поэтому в моем примере одно ограничение будет содержать полное декартово произведение символов выше. И второе ограничение - это «[ab] .c»; это второе ограничение уменьшает количество допустимых комбинаций первого ограничения, которое мне нужно рассмотреть.

Поскольку эти ограничения трудно создать; Я хочу представить себе, как выглядят все комбинации блоков в каждом ограничении, но только действительные комбинации, которые передают все ограничения. Отсюда мой вопрос. Благодаря!

Answer 1

Постарайтесь просто предоставление итератора, который генерирует имена непосредственно для фильтрации, например, так:

import itertools 
import re 

s1 = ['a', 'b'] 
s2 = ['c', 'd', 'e', 'f'] 
s3 = ['c', 'd', 'e', 'f'] 
s4 = ['g'] 

p = itertools.product(*[s1,s2,s3,s4]) 
r = re.compile('[ab].c') 
l = filter(r.search, (''.join(s) for s in p)) 
print(list(l)) 

Таким образом, он не должен собрать полный набор комбинаций в памяти, он будет держать только те, соответствуют критериям. Возможно, есть и другой путь.

EDIT:

Одним из основных отличий от оригинала, является то, что вместо того, чтобы:

[''.join(s) for s in p] 

который является списком понимания, мы используем:

(''.join(s) for s in p) 

Какие является генератором.

Важным отличием здесь является то, что понимание списка создает список с использованием назначенных критериев и генератора, в то время как только предоставление генератора позволяет фильтру генерировать значения по мере необходимости. Важным механизмом является lazy evaluation, который действительно просто сводится только к оценке выражений по мере того, как их значения становятся необходимыми.

Answer 2

Переключение из списка в генератор, ответ Роба экономит место, но не время (по крайней мере, не асимптотически). Вы задали очень широкий вопрос о том, как перечислить все решения для того, что по существу является constraint satisfaction problem. Большие победы придут от принудительного применения local consistency, но трудно дать вам совет без особых знаний о ваших ограничениях.