Хеш 8-значный номер, который содержит неповторяющиеся цифры только от 1 до 8

Question

Учитывая, что число может содержать только цифры от 1 до 8 (без повторения) и имеет длину 8, как мы можем хешировать такие числа, не используя hashSet?

Мы не можем просто напрямую использовать значение числа значения хеширования, так как размер стека программы ограничен. (Под этим я подразумеваю, что мы не можем напрямую сделать индекс массива, представляющий наше число).

Следовательно, это 8-значное число должно быть сопоставлено максимально с 5-значным числом.

Я видел этот ответ. Функция hash возвращает 8-значный номер для входа, который представляет собой 8-значный номер.

Итак, что я могу сделать здесь?

Answer 1

kamoroso94 дали мне идею представить число в восьмеричном виде. Номер остается уникальным, если убрать из него первую цифру. Таким образом, мы можем создать массив длиной 8^7=2097152 и, таким образом, использовать восьмеричную семизначную версию в качестве индекса.

Если этот размер массива больше стека, то мы можем использовать только 6 цифр ввода, преобразовать их в восьмеричные значения. Итак, 8^6=262144, это довольно мало. Мы можем сделать двумерный массив длиной 8^6. Таким образом, общее используемое пространство будет порядка 2*(8^6). Первый индекс второго измерения представляет, что число начинается с меньшего числа, а второй индекс представляет, что число начинается с большего числа.

Answer 2

Есть несколько вещей, которые вы можете сделать. Вы можете вычесть 1 из каждой цифры и проанализировать ее как восьмеричное число, которое сопоставит однозначное число каждого вашего домена с диапазоном [0,16777216) без пробелов. Полученное число можно использовать как индекс в очень большом массиве. Пример этого может работать следующим образом:

function hash(num) {
  return parseInt(num
    .toString()
    .split('')
    .map(x => x - 1), 8);
}

const set = new Array(8**8);
set[hash(12345678)] = true;
// 12345678 is in the set

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

---

Редактировать : После просмотра обновленного вопроса я начал думать о том, как можно сопоставить число с его положением в лексикографически отсортированном списке перестановок цифр 1-8. Это было бы оптимальным, потому что дает теоретический 5-значный хеш, который вы хотите (до 40320). У меня были некоторые проблемы с формулировкой алгоритма, чтобы сделать это самостоятельно, поэтому я немного покопался. Я нашел пример реализации , который делает именно то, что вы ищете. Я черпал вдохновение для реализации этого алгоритма на JavaScript для вас.

function hash(num) {
  const digits = num
    .toString()
    .split('')
    .map(x => x - 1);
  const len = digits.length;
  const seen = new Array(len);
  let rank = 0;

  for(let i = 0; i < len; i++) {
    seen[digits[i]] = true;
    rank += numsBelowUnseen(digits[i], seen) * fact(len - i - 1);
  }

  return rank;
}

// count unseen digits less than n
function numsBelowUnseen(n, seen) {
  let count = 0;
  for(let i = 0; i < n; i++) {
    if(!seen[i]) count++;
  }
  return count;
}

// factorial fuction
function fact(x) {
  return x <= 0 ? 1 : x * fact(x - 1);
}