given the following hash table with linear probing when the hash function is: $$k mod 10$$

enter image description here

how many different sequences will produce the given table? (starting from an empty table)

  • $\begingroup$ I believe thirty sequences. What do you think? $\endgroup$ – Hendrik Jan May 2 '18 at 12:15
  • $\begingroup$ I believe you're right! How did you get to this? $\endgroup$ – user112112 May 2 '18 at 12:29
  • $\begingroup$ I got 30, as well. The elements at 2, 3, 4 and 6 can be inserted in any order, so you get 4! = 24 sequences. Of these 24, there are exactly 6 permutations where the element at 6 is last. In this case, the element at 5 can be inserted either before or after the element at 6, which adds 6 more sequences. The element at 7 has to be inserted after both the element at 5 and the element at 6, so no more new sequences exist due to the element at 7. $\endgroup$ – Mike Borkland May 2 '18 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.