11

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

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

Ваша функция должна быть биективной и детерминированной, то есть 1она всегда будет отображаться в определенном списке и 2всегда будет отображаться в другом определенном списке и т. Д.

Ранее мы отображали целые числа в список, состоящий только из 0и 1.

Однако теперь список будет состоять из неотрицательных чисел.

Спекуляции

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

счет

Это код-гольф . Самый низкий балл побеждает.

Оценка - это сумма длин (в байтах) двух программ / функций.

code-golf set-theory Дрянная Монахиня
источник

«Однако теперь список будет состоять из неотрицательных чисел».

Утренняя монахиня

Итак, чтобы быть ясным, мы картируем N^inf -> N?

Мего

@Mego N ^ inf не считается. N ^ k, где k - любое конечное число.

Утренняя монахиня

Мы обсуждали это в чате.

Утренняя монахиня

Начинается ли он с 1 или начинается с 0 - ваш выбор. Это относится к одному целому числу и к целым числам в списке.

Деннис

10

Желе , 18 16 байтов

Список в целое число, 10 8 байт

TṪạL;³ÆẸ

Отображает списки неотрицательных целых чисел в положительные целые числа. Попробуйте онлайн!

Целое число в списке, 8 байт

ÆE©Ḣ0ẋ®;

Отображает положительные целые числа в списки неотрицательных целых чисел. Попробуйте онлайн!

Фон

Пусть p ₀ , p ₁ , p ₂ , ⋯ - последовательность простых чисел в порядке возрастания.

Для каждого списка неотрицательных целых чисел A: = [a ₁ , ⋯, a _n ] мы отображаем A в p ₀^{z (A)} p ₁^{a ₁} ⋯ p _n^{a _n} , где z (A) - число конечные нули A .

Перевернуть вышеуказанную карту в прямом смысле. Для положительного целого числа k мы однозначно разлагаем его как произведение последовательных простых степеней n = p ₀^{α ₀} p ₁^{α ₁} ⋯ p _n^{α _n} , где α _n > 0 , затем восстанавливаем список как [α ₁ , ⋯, α _n ] , добавляя α _{0 к} нулю.

Как это работает

Список в целое число

TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.

Целое число в списке

ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.

Пример вывода

Первые сто положительных целых чисел отображаются в следующих списках.

  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]

Деннис
источник

Это великолепно.

Утренняя монахиня

3

Python 2, 88 байт

d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)

Демо-версия:

>>> for i in range(33):
...     print e(d(i)), d(i)
... 
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]

Python 2, 130 байт

Вот более «эффективное» решение, в котором длина в битах на выходе является линейной по длине в битах на входе, а не экспоненциальной.

def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)

Андерс Касеорг
источник

Использует тот же алгоритм, что и мое решение :)

Leaky Nun

@KennyLau: я не смотрел на ваше решение. Они похожи, но не идентичны (0 и 1 поменялись местами). И ваш не может обойти пустой список.

Андерс Касеорг

Понятно, спасибо за напоминание.

Утренняя монахиня

Кстати, я сказал, что вывод может быть в любой базе.

Утренняя монахиня

Поскольку совместное использование кода между функциями разрешена, она выглядит , как вы можете просто построить , eчтобы быть обратным для d: e=lambda l,i=0:l!=d(i)and-~e(l,i+1).

xnor

1

Python 2, 204 202 байта

p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
 if n<1:return[]
 r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r

Работает путем многократного применения биекции Z + x Z + <-> Z + с добавлением длины списка.

0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

orlp
источник

Один вопрос: какая функция является функцией «список в целое число», а какая функция «список в целое»?

user48538

@ zyabin101 e- список в целое число, dцелое число в список (кодирование / декодирование).

orlp

Мне нравится это решение.

Утренняя монахиня

0

Сетчатка, 17 + 23 = 40 байт

Из списка в целое число:

\d+
$&$*0
^
1

1

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

От целого числа до списка:

^1

S`1
m`^(0*)
$.1
¶
<space>

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

Использует алгоритм Kaseorg .

Дрянная Монахиня
источник

Сопоставьте список неопределенного размера с числом!

Спекуляции

счет

Ответы:

Желе , 18 16 байтов

Список в целое число, 10 8 байт

Целое число в списке, 8 байт

Фон

Как это работает

Список в целое число

Целое число в списке

Пример вывода

Python 2, 88 байт

Python 2, 130 байт

Python 2, 204 202 байта

Сетчатка, 17 + 23 = 40 байт