Конечно, есть много способов сделать это.
Для начала необходимо иметь только обратимую функцию, которая объединяет два значения в одно.(Чтобы он был обратимым, должна существовать другая функция, которая принимает выходное значение и воссоздает два входных значения.)
Давайте назовем функцию, которая объединяет два значения combine и обратную функцию separate.Тогда имеем:
separate(combine(a, b)) == [a, b]
для любых значений a и b.Это означает, что combine(a, b) == combine(c, d) может быть истинным, только если a == c и b == d;другими словами, каждая пара входов производит различный вывод.
Кодирование произвольных векторов
Как только мы получим эту функцию, мы можем кодировать входные векторы произвольной длины.Самый простой случай, когда мы заранее знаем, какова длина вектора.Например, мы можем определить:
combine3 = (a, b, c) => combine(combine(a, b), c)
combine4 = (a, b, c, d) => combine(combine(combine(a, b), c), d)
и так далее.Чтобы отменить это вычисление, нам нужно только несколько раз вызвать separate правильное количество раз, каждый раз сохраняя второе возвращаемое значение.Например, если бы мы ранее вычислили:
m = combine4(a, b, c, d)
, мы могли бы получить обратно четыре входных значения следующим образом:
c3, d = separate(m)
c2, c = separate(c3)
a, b = separate(c2)
Но ваш вопрос требует способа объединить произвольное числоценностей.Чтобы сделать это, нам просто нужно сделать один последний combine, который смешивает количество значений.Это позволяет нам вернуть исходный вектор: сначала мы вызываем separate, чтобы вернуть счетчик значений, а затем мы вызываем достаточное количество раз, чтобы извлечь каждое последующее входное значение.
combine_n = v => combine(v.reduce(combine), v.length)
function separate_n(m) {
let [r, n] = separate(m)
let a = Array(n)
for (let i = n - 1; i > 0; --i) [r, a[i]] = separate(r);
a[0] = r;
return a;
}
Обратите внимание, чтодве вышеупомянутые функции не работают с пустым вектором, который должен кодировать 0. Добавление правильных проверок для этого случая оставлено в качестве упражнения.Также обратите внимание на предупреждение внизу этого ответа, о целочисленном переполнении.
Простая функция объединения: диагонализация
После этого давайте рассмотрим, как реализовать combine.На самом деле существует множество решений, но одно довольно простое - использовать функцию диагонализации:
diag(a, b) = (a + b)(a + b + 1)
------------------ + a
2
Это в основном назначает позиции в бесконечном квадрате путем отслеживания последовательных диагоналей:
<-- b -->
0 1 3 6 10 15 21 ...
^ 2 4 7 11 16 22 ...
| 5 8 12 17 23 ...
a 9 13 18 24 ...
| 14 19 25 ...
v 20 26 ...
27 ...
(В более ранней версии этого ответа я перевернул a и b, но эта версия, кажется, имеет несколько более интуитивно понятные выходные значения.)
Обратите внимание, что верхняя строка, где a == 0, этоименно треугольные числа , что неудивительно, потому что уже перечисленные позиции являются верхним левым треугольником квадрата.
Чтобы обратить преобразование, мы начнем с решения уравнения, которое определяет треугольноечисла, m = s(s + 1)/2, что совпадает с
0 = s² + s - 2m
, чье решение можно найти с помощью стандартной квадратичной формулы , в результате чего:
s = floor((-1 + sqrt(1 + 8 * m)) / 2)
(s вот оригинал a+b; то есть индекс диагонали.)
Я должен объяснить вызов floor, который пробрался тудае.s будет точно целым числом только в верхнем ряду квадрата, где a равно 0. Но, конечно, a обычно не будет 0, а m обычно будет немного больше, чемтреугольное число, которое мы ищем, поэтому, когда мы решим для s, мы получим некоторое дробное значение.Floor просто отбрасывает дробную часть, поэтому результатом является диагональный индекс.
Теперь нам просто нужно восстановить a и b, что просто:
a = m - combine(0, s)
b = s - a
Итак, теперь у нас есть определения combine и separate:
let combine = (a, b) => (a + b) * (a + b + 1) / 2 + a
function separate(m) {
let s = Math.floor((-1 + Math.sqrt(1 + 8 * m)) / 2);
let a = m - combine(0, s);
let b = s - a;
return [a, b];
}
Одна замечательная особенность этого конкретного кодирования состоит в том, что каждому неотрицательному целому числу соответствует отдельный вектор.Многие другие схемы кодирования не имеют этого свойства;возможные возвращаемые значения combine_n являются подмножеством набора неотрицательных целых чисел.
Примеры кодировок
Для справки, здесь приведены первые 30 закодированных значений, ивекторы, которые они представляют:
> for (let i = 1; i <= 30; ++i) console.log(i, separate_n(i));
1 [ 0 ]
2 [ 1 ]
3 [ 0, 0 ]
4 [ 1 ]
5 [ 2 ]
6 [ 0, 0, 0 ]
7 [ 0, 1 ]
8 [ 2 ]
9 [ 3 ]
10 [ 0, 0, 0, 0 ]
11 [ 0, 0, 1 ]
12 [ 1, 0 ]
13 [ 3 ]
14 [ 4 ]
15 [ 0, 0, 0, 0, 0 ]
16 [ 0, 0, 0, 1 ]
17 [ 0, 1, 0 ]
18 [ 0, 2 ]
19 [ 4 ]
20 [ 5 ]
21 [ 0, 0, 0, 0, 0, 0 ]
22 [ 0, 0, 0, 0, 1 ]
23 [ 0, 0, 1, 0 ]
24 [ 0, 0, 2 ]
25 [ 1, 1 ]
26 [ 5 ]
27 [ 6 ]
28 [ 0, 0, 0, 0, 0, 0, 0 ]
29 [ 0, 0, 0, 0, 0, 1 ]
30 [ 0, 0, 0, 1, 0 ]
Внимание!
Обратите внимание, что все незакодированные значения довольно малы.Кодированные значения похожи по размеру на конкатенацию всех входных значений и поэтому растут довольно быстро;Вы должны быть осторожны, чтобы не превысить предел Javascript для точных целочисленных вычислений.Как только закодированное значение превысит этот предел (2 53 ), будет невозможно изменить кодировку.Если ваши входные векторы длинные и / или закодированные значения велики, вам нужно найти какую-то поддержку bignum для точных целочисленных вычислений.
Альтернативные функции объединения
Другая возможная реализация combine:
let combine = (a, b) => 2**a * 3**b
Фактически, используя силы простых чисел, мы могли бы обойтись без последовательности combine_n и просто создать комбинацию напрямую:
combine(a, b, c, d, e,...) = 2<sup>a</sup> 3<sup>b</sup> 5<sup>c</sup> 7<sup>d</sup> 11<sup>e</sup> ...
(Это предполагает, что закодированные значения строго положительны; если бы они могли быть 0, у нас не было бы никакого способа узнать, как долго была последовательность, потому что закодированное значение не различаетмежду вектором и тем же вектором с добавленным 0. Но это не большая проблема, потому что если бы нам нужно было иметь дело с 0, мы просто добавили бы один ко всем используемым показателям:
combine(a, b, c, d, e,...) = 2<sup>a+1</sup> 3<sup>b+1</sup> 5<sup>c+1</sup> 7<sup>d+1</sup> 11<sup>e+1</sup> ...
Это, безусловно, правильно и очень элегантно в теоретическом смысле. Это решение, которое вы найдете в теоретических учебниках по КС, потому что это гораздо проще доказать уникальность.универсальность и обратимость.Однако в реальном мире это действительно не практично.Обратная комбинация зависит от нахождения основных факторов кодированного значения, и кодированные значения действительно огромны, выходя за пределы диапазона легко представимых чисел.
Еще одна возможность - это та, которую вы упомянули в вопросе:просто поместите разделитель между последовательными значениями.Один простой способ сделать это - переписать значения для кодирования в базе 9 (или базе 15), а затем увеличить все значения цифр, чтобы цифра 0 не присутствовала ни в одном кодированном значении.Затем мы можем поместить 0 между закодированными значениями и прочитать результат в базе 10 (или базе 16).
Ни одно из этих решений не обладает тем свойством, что каждое неотрицательное целое число является кодировкой некоторого вектора.(Второй почти обладает этим свойством, и это полезное упражнение, чтобы выяснить, какие целые числа не являются возможными кодировками, а затем исправить алгоритм кодирования, чтобы избежать этой проблемы.)