Количество различных последовательностей вставки значений Key в хеш-таблицу

Question

Хеш-таблица длиной 10 использует открытую адресацию с хеш-функцией h(k)=k mod 10 и линейное зондирование. После вставки 8 значений в пустую хеш-таблицу таблица выглядит так, как показано ниже

0 |
1 | 91
2 | 2
3 | 13
4 | 24
5 | 12
6 | 62
7 | 77
8 | 82
9 |

Сколько различных последовательностей вставки значений ключа, использующих одну и ту же хеш-функцию и линейное зондирование, приведут к хеш-таблице, показанной выше?

ОТВЕТ - 128.

Я знаю для 91,2,13,24,77 его 5! = 120, но я не могу понять, какие еще 8 комбинаций?

Answer 1

Данный ответ неверен. На самом деле это был самый надуманный ответ, а ответ, предоставленный источником, неверен. Реальный ответ - 168.

Это можно сделать двумя способами -

1) 91,2,13,24,12,62,77,82 - здесь, если вы видите и отфильтровываете детали

  _,91,_,2_,13,_,24,_,12,_,62,_,82 

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

Теперь 91,2,13,24 могут прийти в любом порядке и могут быть расположены, как указано выше, так что всего путей - 4! и для каждого из 4! аранжировки 77 могут прийти в любом из 7 мест, поэтому ответ - 4! * 7 = 168.

2) Второй способ - есть только 3 возможных последовательности

я) 91,2,13,24,77,12,62,82

 Here 91,2,13,24,77 can come in any order, They will get there respective 
 slots so total 5! ways.

ii) 91,2,13,24,12,77,62,82

  Here 91,2,13,24 can come in any order and we have fixed 77 after 12 so total 
  4! ways.

iii) 91,2,13,24,12,62,77,82

   same here with 4! ways 91,2,13,and 24 can come and 77 is fixed after 62.

итого 5!+4!+4!=168.

Answer 2

Поразмыслив, я пришел к такому выводу. Прежде всего, 12,62,82 — это значения, порядок которых мы не должны нарушать, причина этого в том, что они стремятся к одной и той же позиции. Так, например, если 62 или 82 появились раньше, чем 12, то они займут позицию 12 и окажутся в другом состоянии хеш-таблицы.

Поэтому мы возьмем их как единое целое «12,62,82» с именем DND(НЕ БЕСПОКОИТЬ).

1- Теперь у нас есть 91,2,13,24,77, все они независимы друг от друга, поскольку ищут разные хеш-позиции, назовем их « Халявыми ». Тем временем, DND спокойно сидит за халявными комбинациями.

Всего комбинаций -> 5! => 120.

2- Теперь мы будем по одному забирать элементы из ДНД , не нарушая их собственный порядок, и расселяться с другими -

I -> 12 до 77 -> [гребенка(91,2,13,24), 12, 77, 62, 82] -> 4!

II -> 12,62 до 77 -> [гребенка(91,2,13,24), 12, 62, 77, 82] -> 4!

Всего комбинаций -> 4! * 2.

3. Теперь 91 — это номер, который не будет беспокоить DND . Поставив 91 после «Не беспокоить», мы получим три случая:

I -> DND между 77 и 91 -> [comb(2, 13, 24, 77), DND, 91] -> 4!.

II -> Теперь возмутим DND, возьмем из них элемент 12 и поставим его перед 77 -> [comb(2,13,24), 12, 77, 62, 82, 91] -> 3!

Но я могу поставить 91 перед 82 и 62, что в сумме составит 3 комбинации с 3! Это увеличивает сумму до 3! * 3.

III -> Теперь берем 62 из DND и помещаем их между 12 и 77 -> [comb(2, 13, 24), 12, 62, 77, 82, 91] -> 3!

Опять же, я могу поставить 91 перед 82, что добавит все к 2 комбинациям с 2! ->3! * 2.

Всего комбинаций -> 4! + 3!*5

**Теперь ответ, который появился на картинке: -> 5! + 4!2 + 4! + 3!5 -> 222. Это все, что я смог выяснить. Скажите, пожалуйста, если я сделал что-то не так.