А «рифма схема» представляет собой последовательность букв a
в z
, таким образом, что первые вхождения символов в порядке возрастания (без пробелов), начиная с a
. Например (отмечены первые вхождения):
abccdbebdcfa
^^^ ^ ^ ^
Количество рифмовых схем длины N
определяется числами Белла B(N)
. ( OEIS A000110 )
Соревнование
Ваша задача - реализовать перечисление этих схем рифм, т.е. биективное отображение из целых в рифманные схемы. Вам дано положительное целое число N <= 26
, а также неотрицательное целое число 0 <= i < B(N)
. Кроме того, вы можете использовать диапазон 1 <= i <= B(N)
. Вы должны вывести рифмованную схему длины N
, такую, чтобы каждый i
получал свою строку.
Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).
Вы можете использовать строчные или прописные буквы (последовательно).
Ваш код должен быть в состоянии справиться с любым действительным вкладом в разумном количестве времени (например , не более чем на несколько часов для N = 26
, худшего случая i
). Это должно позволить решениям, которые масштабируются экспоненциально с N
(для небольших баз), даже на медленных языках, но запрещать решения, которые линейно масштабируются с i
(то есть B(N)
). В частности, это означает, что вы не можете просто перебрать все действительные схемы длины рифмы, N
пока не откажетесь от i
схем.
Применяются стандартные правила игры в гольф .
Примеры
Точное назначение i
схем (т. Е. Порядок схем для данного N
) зависит от вас. Но, скажем, вы выбрали лексикографический порядок, ваше решение должно соответствовать следующей таблице (с -
указанием неверного ввода):
N\i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 a - - - - - - - - - - - - - -
2 aa ab - - - - - - - - - - - - -
3 aaa aab aba abb abc - - - - - - - - - -
4 aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd
Вот короткий скрипт CJam, который генерирует все действительные схемы рифмы для любой заданной длины (но не пытайтесь больше 10, или вы будете ждать некоторое время).
Связанные проблемы
источник
N
), при условии, что оно не окажется достаточно тривиальным, и я был просто слишком глуп, чтобы найти его.Ответы:
CJam,
6866 байтПопробуйте онлайн.
Это моя первая программа CJam. Он начал работать как порт моего решения на Perl и изначально был длиной более 130 байт. Дальнейшие предложения по игре в гольф приветствуются.
Как и в моей программе на Perl, она состоит из двух частей.
Для отладки массивов , созданных Часть 1 оных
]_`o~
между Частью 1 и 2. Если п5
, массивы будут выглядеть следующим образом :[[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]
. Индексы 0 каждого массива не используются, они просто облегчают задачу, не требуя вычисления смещений. Массивы рассчитываются так:Он сохраняет копию старого массива при расчете следующего. Массивы читаются и отбрасываются в обратном порядке в части 2.
источник
Python 2, 153
Он использует алфавитный порядок и индексацию на основе 0.
Позвольте
l
обозначить длину суффикса букв иa
обозначить количество различных букв, которые были использованы в предыдущей части. Тогда функция,p(l,a)
которая вычисляет количество способов выбора оставшихся букв, может быть 40 байтов:Однако это слишком медленно для задачи, поэтому вместо этого необходимые значения предварительно рассчитываются и сохраняются в
u
массиве. На каждом этапе вычисления, если следующая буква является той изa
уже использованных, n = k * p (l - 1, a) + n ', где k - это индексированная буквой алфавита, а n' - значениеn
для следующего вызова функции, которое содержит информацию об оставшихся буквах. Если используется новая буква, то n = a * p (l - 1, a) + n ' .источник
Haskell (GHC 7.10), 150 байт
Оператор
n # i
вычисляетi
рифмовую схему th (с нулевым индексом) длиныn
. Он работает в операциях O (n²) (большое целое), используя ленивые бесконечные списки Haskell для автоматического запоминания. Образцы прогонов:(Если бы максимальное N было 25 вместо 26, их
.fromEnum
можно было бы удалить, потому что B (25) помещается в 64-разрядную версиюInt
.)источник
Perl 257 + 1 (флаг -p) = 258Perl 182 + 10 (-pMbignum flags) = 192
Спасибо dev-nul за сохранение большого количества байтов! Теперь я переписал его, основываясь на том, что я узнал из версии CJam.
Вычисляет рифму в порядке возрастания алфавита, 0 проиндексировано.
Две части: Часть 1 составляет
12890 байтов и вычисляет матрицу для Части 2. Часть 2 составляет12992 байта и выполняет несколько простых математических вычислений для вычисления каждой буквы.Если бы я мог избавиться от матрицы и заменить ее двумя простыми числами, я мог бы рассчитать один путь через матрицу для каждого числа и сэкономить много байтов!Видимо, эта идея не работает!К сожалению, он не выводит правильные рифмы для значенийi
выше, чем 9007199254740992, но он прекрасно работает для низких значений!Я добавил библиотеку Bignum стоимостью 11 байт.Он запускается из командной строки сperl -pMbignum bell-rhyme.pl
.-pMbignum
= 10 байт. Это также очень быстро для любого входного значения.источник
Oracle SQL 11.2,
412284283 байтаК сожалению, он работает только до длины 8. Любое большее значение приводит к: ORA-01489: результат объединения строк слишком длинный
Un-golfed
Представление a генерирует буквы: i в столбце a и их значение в b.
Рекурсивное представление v принимает строку, которая создается как параметр v, значение последней буквы, использованной в c, и значение наибольшей буквы, использованной в n. Параметр n равен длине строки без каких-либо повторяющихся букв, для этого и используется регулярное выражение.
Буква действительна, если ее значение <= значение самой большой буквы, которая уже использовалась, или это следующая буква, которая будет использоваться.
Каким-то образом для выполнения запроса требуется часть LENGTH (s) <: n, я должен что-то упустить в том, как работает запрос.
Основной SELECT заботится о фильтрации недопустимых входов и более коротких строк, построенных до достижения заданной длины.
Версия 412 байт
Не пытайтесь выполнить запрос 412 байт с помощью 26. Он переводит базу данных в ограниченный режим, по крайней мере, на моей версии xe, работающей в док-контейнере на MacBook. Я мог бы примерить exadata на работе, но, к сожалению, мне все равно нужно зарабатывать на жизнь.
источник
Mathematica, 136 байт
Для полноты, вот моя справочная реализация в гольфе. В отличие от существующих ответов, это не выполняется за полиномиальное время (оно экспоненциально
N
с базой 2), но соответствует временному ограничению (наихудший случай все равно будет выполняться менее чем за полчаса).Идея заключается в следующем:
Для каждой схемы рифмы мы можем определить позиции, где максимальный символ пока увеличивается:
Мы можем рассматривать эти маркировки как двоичное число, что позволяет легко перебирать все такие структуры. Нам нужно перебрать от 2 n-1 до 2 n (или наоборот), отсюда и экспоненциальная сложность времени.
i
, мы вычитаем его изi
. В противном случае мы нашли структуру запрошенной схемы рифмы.i
(или то, что от него осталось) как смешанное базовое число, где веса цифр определяются количеством разрешенных символов в оставшихся позициях.Интересно, позволит ли это более короткое решение на некоторых других представленных языках, поскольку оно не требует запоминания или предварительного вычисления.
источник