Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

(Sorry about me not being able to explain this problem with perfect mathematical terms) Consider the following data set

its a combination set of 1-77

n1,n2,n2,n4
1,2,3,4
1,2,3,5
1,2,3,6
...........
...........
24,25,26,27
...........
...........
74,75,76,77

total possible combinations is 1,353,275

lets say i randomly select 4 numbers between 1-77 for example (22,56,67,70) and search for the records that has any 3 of these values matching in the above data set i get exactly and always 293 records which is perfect (for any set of random numbers within 1-77).

but lets say i need to introduce an alphabet to the above structure like

n1,n2,n2,n4,char
1,2,3,4,A
1,2,3,5,B
1,2,3,6,C
...........
...........
24,25,26,27,X
...........
...........
74,75,76,77,Y

then if i select 4 random numbers and an alphabet value like (22,56,67,70, M) this messes up the probability and yields different results for different random sets and gets me a range of possible records left or right from 11 (sometimes less than 11 and sometimes more than 11)

the question is how do i reduce the variation and keep it as close to 11 as possible while we have the alphabet in place.

and last we are only considering the set 1,353,275 NOT the entire permutation set with alphabets (1,353,275 X 26)

share|improve this question
    
These are not permutations, these are combinations of 4 objects out of 77. Your count indicates that duplicates are not allowed and order does not matter. How do you choose the letter that goes with each combination? You indicate that there is only one. –  Ross Millikan Oct 14 '13 at 23:26
    
@RossMillikan Thanks for clarifying I'm not from a mathematical background. the letter is choosen randomly and attached to the record. but i make sure that an even set of letters are attached to the entire 1,353,275 in other words there can be only 52,049+-1 for A,B,C...Z –  Ahsan Oct 14 '13 at 23:40

2 Answers 2

up vote 0 down vote accepted

Before the letters, a search for three numbers would find $74$ matches, one with each of the remaining numbers. If the letters are randomly assigned, a search for three numbers and a letter will find on average $\frac {74}{26} \approx 3$ matches, but there will be dispersion on that. To return on average $11$ matches, you could search for three numbers and a letter, require exactly those numbers, but accept letters up to three ahead (going around the circle). So if you search for $A$, you would accept $A,B,C,D$. If you search for $Y$, you would accept $Y,Z,A,B$

Added: you can reduce the variability if you assign the letters more regularly. It would be even smoother if you had $78=3*26$ numbers. But consider the letters to be $0 (A)$ through $25 (Z)$ and assign to each combination the sum of the numbers $\pmod {26}$. Then for combinations where the letter you choose doesn't match your query, you can change each number to three others to match the letter, returning $12$ items (unless one number should be $78$). If the letter aligns with the query, each number can only change to two others and you will return $9$ (including the exact set of four).

share|improve this answer
    
Thanks Ross, but still cannot wrap my head around your solution. if you could explain it in a little more detail i would much appreciate it. –  Ahsan Oct 15 '13 at 0:12
    
Do you see why there will be 74 without the letters? If you do the search with four numbers plus a letter and require three numbers plus the letter to match, you would expect $\frac {293}{26}$ on average, which is $11\frac7{26}$ Basically you have a $\frac 1{26}$ chance that the letters match, so it will reduce the number of returns by that factor. –  Ross Millikan Oct 15 '13 at 0:21
    
Sorry Ross, let me see if i got what you mean, for set 70,71,72,73 assign 0 = A since ((70+71+72+73) mod 26 = 0 ? –  Ahsan Oct 15 '13 at 1:55
    
That is correct –  Ross Millikan Oct 15 '13 at 2:00

If you search for records that have any 3 of your values, you should get a lot more than 11 records returned. For example, if you're looking for any records that contain (22,56,67) then there are 74 such sets (1,22,56,67),(2,22,56,67)...(22,56,67,77). Likewise there would be 74 for each set of three values, although there would be one record (the original set of four) that would be returned in each set that matched three records. So if you just look for sets that contain 3 of your 4 values, you should actually get 293 unique records returned (74+73+73+73).

If you're only getting 11 records returned for each triplet searched, then there is a constraint on your sets of four that is not obvious from the example given. As written, it looks as though $n1\in [1,74],n2\in[2,75], n3\in[3,76], n4\in[4,77] \text{ and } n1<n2<n3<n4$.

It's also not clear how the characters are being added to the sets of numbers. Are you just adding a letter to the end of each record so that the first set of four gets an A, the second gets a B, etc.? In other words, if (1,2,3,4,A) is a set, can (1,2,3,4,B) also be a set?

share|improve this answer
    
You are spot on.. i have edited the question to make it more clearer. Thank you for your valuable input. but i need to figure it out still. so any more insight would be appreciated. –  Ahsan Oct 14 '13 at 23:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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