У меня маленькая проблема с игрушкой, которая беспокоит меня.Я думаю, что это эквивалентно любому числу эквивалентных проблем более серьезного характера.Нет, это не домашнее задание или вопрос об интервью ... хотя, возможно, я буду использовать его для опроса людей в какой-то момент, если почувствую, что знаю оптимальное доказуемое решение.
Я выучил слово supervocalic (прилагательное, описывающее слово или фразу, содержащую каждый из пяти гласных - A, E, I, O и U - ровно один раз).Примерами являются «вопросительный знак», «амбидекстовый» и, конечно, «супервокальный».
Я написал небольшую программу на Python для определения супервокальных слов .Это было достаточно просто, и суть этого:
matches = {}
for w in words:
pat = tuple(w.count(v) for v in vowels)
if pat in matches:
matches[pat].add(w)
else:
matches[pat] = {w}
words просто из большого моего списка слов (словарь скрэббл SOWPODS, около 270 тыс. Слов. Я могу просто определить супервокальные слова)с matches[(1,1,1,1,1)] ... т. е. каковы слова с ровно одним из каждого гласного. FWIW, vowels технически конфигурируем здесь, так что мой маленький скрипт может сделать эквивалентную вещь для любого подмножества символов (и любого списка слов).
Моя проблема в том, что я хотел бы найти все супервокальные нграммы . Слова 1 грамма. Что 2 грамма, 3 грамма и т. Д., Которые также делаютсупер-вокальные фразы. Оказывается, у меня 175 слов без AEIOU, так что технически каждый элемент powerset может быть добавлен к каждой ngram, которая не включает их. Это очень много.
Но игнорируя эти 2^ 175 дополнительных вариаций каждой «заполненной» супервокальной фразы, как мне объединить счетные числа. Есть много эквивалентных слов с точки зрения количества гласных, так что конечноКомбинации at, например:
pat: (1, 0, 1, 0, 0); numwords: 5499
pat: (0, 1, 0, 1, 1); numwords: 2703
Таким образом, любой из первой перечисленной группы и любой другой из второй перечисленной группы имеют право.Это 14,863,797 2 грамма прямо там.На самом деле, вдвое больше, так как любой порядок в порядке.
Давайте также предположим, что я выбросил каждый паттерн с любым элементом больше, чем одним, что было бы словами, которые нельзя включить ни в одну супервокальную фразу, потому что они слишком«богатые гласными» все сами по себе.
Я вижу по глазному яблоку, что (1, 0, 1, 0, 0) и (0, 1, 0, 1, 1) являются дополнительными паттернами, которые вместе будут «заполнять» пространство гласных (или любое пространство элементов в общей версии).проблемы).Для произвольных кортежей любой длины, как мне найти все коллекции кортежей N-размера, которые будут объединяться как «заполненные кортежи» (но не как переполненные)?
По сути, несмотря на предварительный вывод, этоМоя задача найти эти дополнительные коллекции кортежей N-размера ... наиболее эффективным способом, возможным для произвольной длины кортежа, а не только для длины 5. Несмотря на то, что я предпочитаю Python и мой короткий фрагмент кода, этот вопрос должен применяться к довольномного любого языка программирования.