0
$\begingroup$

my data's range is from 1 to 9 and I have two subsets of integers from this range. the hash function takes each of this subsets and calculate product of these three integers and maps this set to the result of this multiplication.I want to know the probability of collision by this hash function with this two subsets of integers that they are from 1 to 9 and the size of each subset equals 3.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – Apass.Jack Jan 4 at 13:27
  • $\begingroup$ we have C(9,3) = 84 situations and the least multiplication that can occur is 1*2*3=6 and the greatest is 9*8*7=504.but I can't calculate the multiplication result for each situation and then see if two or more situations like 2*6*1=12 and 3*4*1=12 have the same result or not.I am looking for a better way.if you can give me some hint I'll be appreciated. $\endgroup$ – mohamadreza Jan 4 at 13:36
  • $\begingroup$ I do not see any easy and fast method by hand. However, you can probably write a program in your favorite programming language in several minutes to compute the result, which is more likely to be faster and correct. $\endgroup$ – Apass.Jack Jan 4 at 13:47
  • $\begingroup$ I am going to brute-force this by using Python $\endgroup$ – MilkyWay90 Jan 4 at 18:15
  • $\begingroup$ Is something like {8,7,9} and {9,8,7} the same? $\endgroup$ – MilkyWay90 Jan 4 at 18:24
0
$\begingroup$

Here is a Python program that uses brute-force to compute the probability of hash collision of two randomly-chosen different 3-element subsets of $\{1,2,3,4,5,6,7,8,9\}$.

Here is the output of the program.

6 [(1, 2, 3)]
8 [(1, 2, 4)]
10 [(1, 2, 5)]
12 [(1, 2, 6), (1, 3, 4)]
14 [(1, 2, 7)]
16 [(1, 2, 8)]
18 [(1, 2, 9), (1, 3, 6)]
15 [(1, 3, 5)]
21 [(1, 3, 7)]
24 [(1, 3, 8), (1, 4, 6), (2, 3, 4)]
27 [(1, 3, 9)]
20 [(1, 4, 5)]
28 [(1, 4, 7)]
32 [(1, 4, 8)]
36 [(1, 4, 9), (2, 3, 6)]
30 [(1, 5, 6), (2, 3, 5)]
35 [(1, 5, 7)]
40 [(1, 5, 8), (2, 4, 5)]
45 [(1, 5, 9)]
42 [(1, 6, 7), (2, 3, 7)]
48 [(1, 6, 8), (2, 3, 8), (2, 4, 6)]
54 [(1, 6, 9), (2, 3, 9)]
56 [(1, 7, 8), (2, 4, 7)]
63 [(1, 7, 9)]
72 [(1, 8, 9), (2, 4, 9), (3, 4, 6)]
64 [(2, 4, 8)]
60 [(2, 5, 6), (3, 4, 5)]
70 [(2, 5, 7)]
80 [(2, 5, 8)]
90 [(2, 5, 9), (3, 5, 6)]
84 [(2, 6, 7), (3, 4, 7)]
96 [(2, 6, 8), (3, 4, 8)]
108 [(2, 6, 9), (3, 4, 9)]
112 [(2, 7, 8)]
126 [(2, 7, 9), (3, 6, 7)]
144 [(2, 8, 9), (3, 6, 8)]
105 [(3, 5, 7)]
120 [(3, 5, 8), (4, 5, 6)]
135 [(3, 5, 9)]
162 [(3, 6, 9)]
168 [(3, 7, 8), (4, 6, 7)]
189 [(3, 7, 9)]
216 [(3, 8, 9), (4, 6, 9)]
140 [(4, 5, 7)]
160 [(4, 5, 8)]
180 [(4, 5, 9)]
192 [(4, 6, 8)]
224 [(4, 7, 8)]
252 [(4, 7, 9)]
288 [(4, 8, 9)]
210 [(5, 6, 7)]
240 [(5, 6, 8)]
270 [(5, 6, 9)]
280 [(5, 7, 8)]
315 [(5, 7, 9)]
360 [(5, 8, 9)]
336 [(6, 7, 8)]
378 [(6, 7, 9)]
432 [(6, 8, 9)]
504 [(7, 8, 9)]
3-element subsets: 84
total pairs: 3486
duplicity:  27
probability: 0.00774526678141136

The last line of the above output shows the wanted probability is $\dfrac{27}{3486}\approx 0.0077$.

I do not see any mathematical technique that can lead to an easy and fast calculation by hand. If we are asked to compute that kind of probability for many-element subsets such as 10-elements subsets of $\{1,2,\cdots, 40\}$, we might be motivated to find a more efficient solution such as using integer factorization or some algorithms from the problem of subset sums, which may or may not be useful. Otherwise, a program that takes several minutes to write and less than a second to run is the perfect usage of our programming ability and our computers.

$\endgroup$
0
$\begingroup$

I made a program to brute force this.

This means that a very close low bound of this would be $\frac{36}{441}$, so a not that big chance.

If you wanted to avoid overlaps, I suggest you either use a different algorithm or block out all the duplicates, because the chance of this overlapping is pretty high ($8\%$).

$\endgroup$
  • $\begingroup$ thanks for your help.but I wonder if there is a mathematically approach to do this or not? $\endgroup$ – mohamadreza Jan 4 at 18:53
  • $\begingroup$ @mohamadreza There probably is, but I don't know $\endgroup$ – MilkyWay90 Jan 4 at 18:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.