Отображение двух целых чисел одному, уникальным и детерминированным способом
public static int GetQuarter(DateTime date)
{
int[] quarters = new int[] { 4,4,4,1,1,1,2,2,2,3,3,3 };
return quarters[date.Month-1];
}
9 ответов
Вы ищете биективное NxN -> N отображение. Они используются, например, ласточкин хвост . Взгляните на этот PDF-файл , чтобы познакомиться с так называемыми парными функциями . Википедия вводит особую функцию сопряжения, а именно функцию сопряжения Кантора :
Три замечания:
- Как пояснили другие, если вы планируете реализовать функцию сопряжения, вы вскоре можете обнаружить, что вам нужно произвольно большие целые числа (bignums).
- Если вы не хотите делать различие между парами (a, b) и (b, a), то отсортируйте a и b перед применением функции спаривания.
- На самом деле я солгал. Вы ищете биективное отображение
ZxZ -> N. Функция Кантора работает только с неотрицательными числами. Однако это не проблема, потому что биекциюf: Z -> Nлегко определить следующим образом: вскоре вы можете обнаружить, что вам нужны произвольно большие целые числа (bignums). - Если вы не хотите проводить различие между парами (a, b) и (b, a), то отсортируйте a и b перед применением пары функция
- На самом деле я солгал. Вы ищете биективное отображение
ZxZ -> N. Функция Кантора работает только с неотрицательными числами. Однако это не проблема, потому что биекциюf: Z -> Nлегко определить следующим образом: вскоре вы можете обнаружить, что вам нужны произвольно большие целые числа (bignums). - Если вы не хотите проводить различие между парами (a, b) и (b, a), то отсортируйте a и b перед применением пары функция
- На самом деле я солгал. Вы ищете биективное отображение
ZxZ -> N. Функция Кантора работает только с неотрицательными числами. Однако это не проблема, потому что биекциюf: Z -> Nлегко определить следующим образом:- f (n) = n * 2 , если n> = 0
- f (n) = -n * 2 - 1 , если n <0
Стандартный математический способ для положительных целых чисел - использовать уникальность разложения на простые множители.
f( x, y ) -> 2^x * 3^y
Обратной стороной является то, что изображение имеет тенденцию охватывать довольно большой диапазон целых чисел, поэтому, когда дело доходит до выражения При отображении в компьютерном алгоритме у вас могут возникнуть проблемы с выбором подходящего типа для результата.
Вы можете изменить это, чтобы иметь дело с отрицательными x и y , кодируя флаги с степень 5 и 7.
например
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
Что вы предлагаете невозможно. У вас всегда будут коллизии.
Чтобы сопоставить два объекта с другим одиночным набором, сопоставленный набор должен иметь минимальный размер ожидаемого числа комбинаций:
Предполагая 32-битное целое число, у вас есть 2147483647 положительных целых чисел . Выбор двух из них, где порядок не имеет значения и с повторением, дает 2305843008139952128 комбинаций. Это не очень хорошо подходит для набора 32-битных целых чисел.
Однако вы можете уместить это отображение в 61 бит. Вероятно, проще всего использовать 64-битное целое число.
Пусть номер a будет первым, b вторым. Пусть p будет a + 1 -м простым числом, q будет b + 1 -м простым числом
Тогда , результатом будет pq , если a 2pq , если a> b . Если a = b , пусть это будет p ^ 2 .
Если A и B можно выразить двумя байтами, вы можете объединить их в 4 байта. Поместите A в старшую половину и B в младшую половину.
В языке C это дает (при условии, что sizeof (short) = 2 и sizeof (int) = 4):
int combine(short A, short B)
{
return A<<16 | B;
}
short getA(int C)
{
return C>>16;
}
short getB(int C)
{
return C & 0xFFFF;
}
Возможно ли это вообще?
Вы объединяете два целых числа. Оба они имеют диапазон от -2 147 483 648 до 2 147 483 647, но вы возьмете только положительные.
Получается 2147483647 ^ 2 = 4,61169E + 18 комбинаций.
Поскольку каждая комбинация должна быть уникальной и приводить к целому числу, вам понадобится какое-то магическое целое число, которое может содержать такое количество чисел.
Или моя логика ошибочна?
Проверьте это: http://en.wikipedia.org/wiki/Pigeonhole_principle . Если A, B и C одного типа, это невозможно. Если A и B - 16-битные целые числа, а C - 32-битные, то вы можете просто использовать сдвиг.
Сама природа алгоритмов хеширования заключается в том, что они не могут предоставить уникальный хэш для каждого отдельного ввода.
Построить отображение не так уж и сложно:
1 2 3 4 5 use this mapping if (a,b) != (b,a)
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40
1 2 3 4 5 use this mapping if (a,b) == (b,a) (mirror)
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24
0 1 -1 2 -2 use this if you need negative/positive
0 0 1 2 4 6
1 1 3 5 7 10
-1 2 5 8 11 14
2 4 8 11 15 19
-2 6 10 14 19 24
Выяснить, как получить значение для произвольных a, b, немного сложнее.
f (a, б) = s (a + b) + a , где s (n) = n * (n + 1) / 2
- Это функция - она детерминирована.
- Это также инъективно - f отображает разные значения для разных пар (a, b). Вы можете доказать
это используя факт:
s (a + b + 1) -s (a + b) = a + b + 1 . - Он возвращает довольно маленькие значения - хорошо, если вы собираетесь использовать его для индексации массива, поскольку массив не обязательно должен быть большим.
- Это удобно для кеширования - если две пары (a, b) расположены близко друг к другу, тогда f сопоставляет им числа, которые близки друг к другу (по сравнению с другими методами).
Я не понял что Вы имеете в виду под:
всегда должно давать целое число на либо положительный, либо отрицательный сторона целых чисел
Как я могу написать (больше чем), (меньше чем) символы в этом форуме?