1
$\begingroup$

I'll try to formulate my problem through an example. Lets suppose we have a collection of items of type a,b,c,d,e,f.

a1, a5, a7
b2, b3
c5, c6, c7, c8
d4, d5
e1, e2, e3
f3, f7, f8

If we take one element from each type there are 3*2*4*2*3*3 abcdef lines (combinations).

We have another random line a1b5c7d1e5f7.

I want to count how many from the combinations lines differ by the current line in exactly 3 elements. I.e these lines differ only in one (the first) element

a5b5c7d1e5f7
a8b5c7d1e5f7

I want to do that if it's possible without generating and comparing each combination.

$\endgroup$
2
$\begingroup$

The trick to this count is to fix the elements that will be different, then calculate how many different choices we have for this set of elements. For each selected element we will have one less choice then we did originally, and for the elements which are to be the same we have one choice for that character. Let $V$ be the vector of the character set counts for the positions. In your example we would have $V=[3,2,4,2,3,3]$ and let $t$ be the number of differences. For each t-tuple $x$ (set of t positions) we have $\prod_{i \in x} (V[i]-1)$ strings which differ in exactly those places. The final answer is the sum of this for every t-subset of the positions. Since you character set differs for each position you will need to go through all of the t-tuples to solve this. That is not overly bad since though since the number of t-tuples is polynomial instead of exponential as checking all combinations could have been.

$\endgroup$
  • $\begingroup$ Thank you. I see what you mean. I think the number of t-tuples growths exponentially. $\endgroup$ – albert Dec 21 '16 at 15:50
  • $\begingroup$ @albert for a set of size $n$ ( the length of the string so 6 in your ex) and there are ${n}\choose{t}$ t-tuples which is $O(n^t)$. it depends on what your value of t is, and if it it depends on n or not. With t-tuples we consider t to be a constant, however the largest case will be $t=n/2$ in which case since we define $t$ based on $n$ it would be $O(n^{n/2})$ which is exponential. So unless we define $t$ in terms on $n$ it will be polynomial. $\endgroup$ – lPlant Dec 21 '16 at 17:45

Your Answer

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

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