Codegolf — Биективное Отображение Целых Чисел На Переменное Количество Тритов

Эта задача представляет собой более сложную версию Вот этот.

Переменное количество тритов — это массив из 0 или более тритов (трит — это тройной цифра). Так [] is a variable number of trits, but so is 0*3^2 + 1*3^1 + 2*3^0 = 5 .

Напишите функцию или программу, которая по заданному неотрицательному целому числу возвращает переменное количество тритов, так что каждое целое число имеет взаимно однозначное (биективное) сопоставление с массивом.

Существует бесконечное количество таких отображений, вы вольны строить их по своему усмотрению, но это должен быть один в один. Ваше картографирование должно концептуально быть один к одному для целого числа произвольного размера, но это нормально, если ваш выполнение не работает для больших целых чисел из-за числовых ограничений типов на предпочитаемом вами языке (например, C [0, 1, 2] ).

В качестве примера того, что такое нет сопоставление один к одному — это просто перечисление троичных цифр целого числа. В такой системе 5 становится 1*3^1 + 2*3^0 = 5 (because [1, 2] ), но это не однозначно, потому что int also means 5 (because [] ).

Должно быть совершенно очевидно, что отображение не является взаимно однозначным, если оно пропускает целое число (например, оно не работает для 5), но я хотел бы прояснить, что пропуск массива переменных trit также не является одним из них. -к одному. Вы должны сопоставить все возможные переменные массива trit, включая [0, 2, 2, 1] .

Бонусный вызов

Вы будете награждены официальной наградой Super Smaht® Award™, если ваш ответ будет включать в себя алгоритм (не обязательно в вашей программе игры в гольф), который работает не только для базы 2 или 3, но и для всех баз.

Выигрывает самый короткий код в байтах.

#код-гольф #целое число

Пиф, 6 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 b=>n=>(-~n*~-b).toString(b).slice(1)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Объяснение:

Тестовый набор

Обратная функция: Pyth, 14 байт.

Объяснение:

Тестовый набор

Биекция выглядит следующим образом:

Общая база

Чтобы это работало в любой базе b, просто замените 1 with b, a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...] с (b - 1) и 1 with 1 (б − 1).

JavaScript, 24 байта

Попробуйте онлайн!

Орудия стандартная троичная биективная нумерация, за исключением случаев, когда цифры уменьшены на 1.

Как это работает: сначала проверьте, a is 0, returning the empty string if so. Otherwise, a(n) предварительно уменьшается, и это значение делится на 3 и округляется в меньшую сторону ( n is a short way to do the rounding) and passed recursively to 9 – последняя цифра будет составлять 1, 2 или 3, а остальные будут кратны 3, поэтому \$\lfloor\frac{n-1}{3}\rfloor\$ — это значение, которое должны неконечные цифры представляют самостоятельно. Окончательно, 5 appends the final digit, reduced by 1 from the standard ( 5 уже уменьшено).

Желе, 3 байта

Попробуйте онлайн!

Инверсный, 3 байта

Попробуйте онлайн!

Обе версии можно заставить использовать произвольную базу, удалив 2 .

Желе, 12 байт

В Jelly нет пустого списка; оно представлено как 1 (an integer not a list).

Для других баз: изменить [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...] to 1 и 1 to [0,1,1] , где 1011 is the intended base.

Попробуйте онлайн!

Тестовый набор.

Для других баз

Это стоит всего 11 байт если указана база в качестве второго входа.

Попробуйте онлайн!

Тестовый набор.

Алгоритм

Я подумал о добавлении 2011 before the list and then convert it to a ternary.

Таким образом, 1000 = 27 will become [0,0,0] пока 100 = 9 will become [0,0] .

Однако возникает проблема: что 1 and n оба сопоставляются с bn .

мне нужно только числа, троичное представление которых начинается с b3 .

Поэтому я сгенерировал те, у которых троичное представление начинается с ×n , and then use their индекс вместо.

То есть список начинается как Ḥ .

Поэтому:

• 0 will be mapped to ḤR‘b3Ḣ’$Ðḟị@
• 3 will be mapped to ‘ Increment all digits ḅ3 Convert from base 3
• ‘ḅ3 will be mapped to ḃ3 Convert to bijective base 3 ’ Decrement all digits
• ḃ3’ will be mapped to n
• n%3 will be mapped to f
• |0 will be mapped to n где n is that list.

Есть еще одна проблема: оба f=n=>n?f(--n/3|0)+n%3:'' and * отображаются в пустой список. Поэтому я удалил y from the list, making 2 .

Это целые числа, троичное представление которых начинается с 3 , кроме 0: [] 1: [1] 2: [0] 3: [2] 4: [0, 1] 5: [1, 0] 6: [1, 2] 7: [2, 1] 8: [0, 0] 9: [0, 2] 10: [1, 1] 11: [2, 0] 12: [2, 2] 13: [0, 0, 1] 14: [0, 1, 0] 15: [0, 1, 2] 16: [0, 2, 1] 17: [1, 0, 0] 18: [1, 0, 2] 19: [1, 1, 1] ⋮ .

Тот же алгоритм можно применить и к другим базам.

Желе, 6 байт

Перевод Ответ Касеорга на Пите.

Попробуйте онлайн!

Жестко закодированная база: попробуйте онлайн!

Дана база: попробуйте онлайн!

CJam, 9 байт

Перевод Ответ Касеорга на Пите.

Попробуйте онлайн!

JavaScript (ES6), 31 байт

Поскольку все остальные переводят прекрасный ответ @AndreasKaseorg. Общая версия (36 байт):