#terminology #representation
#терминология #представление
Вопрос:
Рассмотрим отсортированный список чисел, который «сокращен», так что он увеличивается за исключением одного скачка. Например, порядок может быть,
11, 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Какие типы данных естественным образом имеют это представление, с одним или, возможно, многими «сокращениями», скрывающими порядок по умолчанию? Единственное, что я могу придумать, это колода карт, но в интервью меня попросили привести примеры данных, которые могли бы выглядеть подобным образом. Прошло несколько недель, а я все еще не могу вспомнить ни одного, но мое любопытство берет верх.
Существует ли специальное название для такого рода данных? Я попытался погуглить «вырезать данные», но это, очевидно, не сработало.
Приветствуется любая информация.
[Редактировать] Из приведенных ниже обсуждений это, по-видимому, имеет некоторые интересные взаимосвязи с группами симметрии, и какие виды перестановок возможны только с помощью операции cut. Возможно, мне придется спросить моих местных математиков, что я могу с этим сделать.
Комментарии:
1. Час дня? День месяца? Положение в градусах точки на вращающемся волчке?
2. Я не имею в виду данные, которые циклически изменяются, я имею в виду данные, которые упорядочиваются, а затем вырезаются. Что-то вроде списка дней месяцев в календарном году упорядочено по тому, какой это месяц, и, хотя вы, вероятно, могли бы манипулировать им с достаточным количеством сокращений, чтобы вернуть его к отсортированному списку целых чисел, это, безусловно, не является полезным представлением этих данных. Представьте себе новую колоду карт, которая разрезается четыре раза. Сначала они сортируются, а затем эта сортировка искажается и передается кому-то другому для обработки.
Ответ №1:
Я могу вспомнить несколько из них навскидку.
Первый — это час дня, когда он переходит в новый день: ... 22 23 0 1 2 ... .
Второе — это альфа-упорядочение имен файлов: pax1 pax10 pax11 ... pax19 pax2 pax20 ... .
Еще один пример — месяцы финансового года (в Австралии большинство компаний завершают свой финансовый год в конце июня): 7 8 9 10 11 12 1 2 3 4 5 6 .
Комментарии:
1. Вторые два хороши. Я думаю, что имена файлов, если это действительно вырезанные данные, были бы идеальным примером! Мне придется изучить это подробнее, чтобы определить, может ли каждый естественно отсортированный список файлов быть вырезан по шаблону, который вы встретили, потому что для меня совсем не очевидно, что это так.
2. @Bean, будет только одно сокращение, если есть один переход (например,
pax2черезpax11передачу10 11 2 3 4 5 6 7 8 9), поэтому оно подходит только для определенных комбинаций файлов. Месяцы, вероятно, лучший выбор, поскольку они гарантированно ограничены этим числом для данного финансового года.3. Я не верю, что имена файлов работают как вырезанные данные. Рассмотрим следующий список строк [«pax1», «pax10», «pax2»], которые никогда не могут быть сокращены таким образом, чтобы получались [«pax1», «pax2», «pax10»]…
4. Да, я думаю, мы пришли к одному и тому же выводу в одно и то же время. Тем не менее, небольшие списки данных не требуют какой-либо специальной обработки, так что, например, хотя я мог бы оптимизировать двоичный поиск для вырезанных данных, это пустая трата времени для списка месяцев или часов…
5. @Bean, смотри мой предыдущий комментарий. Это будет работать для ограниченных строк, а не для всех из них. Данные, которые естественным образом обладают этим свойством, — это числа от 2 до 11 (или от 2 до любого подростка до 19), отсортированные в алфавитном порядке. Из-за ограниченных возможностей я предложил использовать месяцы в календарном году. Было бы лучше.
Ответ №2:
После быстрого анализа становится очевидным, что любая последовательность «сокращений» приводит к одному сокращению по отношению к другому индексу. На самом деле, значение имеет только самая последняя точка вырезания, поскольку это значение окажется в начале списка, и это будет эквивалентно вырезанию этих данных из исходного индекса этого элемента.
Так что не так уж и интересно.