Sure @ VS !
Ok let's first check what actually given in the question -:
Given:
(i) Open addressing, Linear probing.
(ii) Hash function h(k) = k mod n , where n=10.
(iii) all slots are initially empty
Find: No. of different insertion sequence possible to achieve given hash table ( It's actually permutation question)
Carefully look at the hash table you will find [ 12, 62, 82 ] will come always in this sequence only because of slot no. (here 'h' represent the hash table) h[2] would be filled with key 2.
Now we take some case step by step.
[ 91, 2, 13, 24, 77 ] [ 12, 62, 82]
case (i) [ 91, 2, 13, 24, 77 ] [ 12, 62, 82], in this step just we fixed the last unbolded sequence and try to arrange the Bolded sequence So in how many ways we can arrange the first Bolded partition = 5! = (120 ways)
case (ii) Now take we are trying to take one element out of the first portion, So here you visualize we can take out only two elements 91, 77 and remaining elements 2, 13 24 we can not take out because of after key value 2 two gaps are in the hash table must be filled up with 13, 24 then only you can fill key 12 in given location in the hash table.
Now take first element 91 out from the first portion and insert in the possible gap of the second portion( unbolded portion) which is 3 [ 12 _ 62 _ 82 _].
So total way to arrange them would be =
3( possible gaps in the second portion) * 4! (arrange the first portion ) = (72 ways)
case (iii) Now take first element 77 out from the first portion and insert in the possible gap of the second portion( unbolded portion) which is 2 [ 12 _ 62 _ 82] because of after 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong.
So total way to arrange them would be =
2( possible gaps in the second portion) * 4! (arrange the first portion ) = (48 ways)
case (iv) Now take both elements 77 and 91 out from the first portion and insert in the possible chance of the second portion( unbolded portion) which is 8 { [ 12 , __77__, 62 __ 82 __ ] = 4, [ 12 , __, 62 , __,77__ , 82 __ ] = 4 } but after 82 you can not put 77 otherwise h[7] will fill up with 82 which would be wrong.
So total way to arrange them would be =
8 * ( possible chance in the second portion) * 3! (arrange the first portion ) = (48 ways)
So total possible ways of sequence
case(i) + case(ii) + case(iii) + case(iv) = 120+ 72+ 48+ 48 = (288) ans.
I hope it will help you to understand [ thumb up] :)
Please if you find anything wrong, you are welcome!!