0
$\begingroup$

This was an algorithm problem but I am having problems in formulating it.

I have a certain approach but I do not know how to fully execute:

Given

  • 26 letters in total
  • All possible strings of length n

Example

Find all possible strings of length 5 such that given [{a, b, c}, {d, g, h}], no two letters from each set can occur in that string:

  • 'a' and 'd' can occur any number of times in the string, as well as 'a' and 'g'.
  • no single instance of 'a' and 'b' occurring or 'b' and 'c' or 'a', 'b' and 'c' ( basically any pair )
  • No two sets will have any characters in common such as [{a, b, c}, {d, g, h}, {c, l, f}] not allowed.

My naive approach

  • Find all possible strings of length n consisting of characters other than the ones mentioned in the set of sets.
  • Take a single set:
    • Take 1 character from a set.
      • Find the characters that are valid with this character and count the possible strings of length n.

But this does not take care of repetitions I think. So is there some other way or do I need to refine more?

$\endgroup$
4
  • $\begingroup$ Do you need to output all such strings or just count them? Also the input to your problem is probably wrong since 1) you say that the input has "All possible strings of length n" but that's an exponential number of strings w.r.t. $n$. You probably just receive $n$ as input. 2) The collection of sets does not appear to be part of the input. $\endgroup$
    – Steven
    Jul 24 '21 at 12:49
  • 1
    $\begingroup$ I'm also confused about the "No non trivial sets such as [{a, b, c}, {d, g, h}, {c, l, f}] because that can be written as [{a, b, c, l, f}, {d, g, h}]". The former multiset permits strings including both "a" and "f", but the latter does not. Does this criteria just mean that all of the input sets are mutually exclusive? $\endgroup$ Jul 25 '21 at 0:24
  • $\begingroup$ @Steven I have to count them as in the question "total no. of" $\endgroup$ Aug 5 '21 at 15:28
  • $\begingroup$ @Throckmorton I wanted to convey something else but I end up writing a wrong condition, I have corrected it now! $\endgroup$ Aug 5 '21 at 15:28
0
$\begingroup$

Let $n$ be the desired length of the strings to build. Then, let $S_1, S_2, \ldots, S_k$ be the sets constraining the solution. We need to choose a total of $n$ letters, by choosing zero or one letter from each set, and possibly repeating the chosen letter. Then, we need to count all the possible ways of rearranging said choices. This means that for each set $S_i$, we have three choices: how many times we will use a letter from that set, which of the $|S_i|$ letters will it be, and where in the string are those letter going to appear.

Assume we will use a letter from $S_1$ exactly $\ell$ times. We have $|S_1|$ choices for said letter, ${n \choose \ell}$ choices for where to put the $\ell$ ocurrences, and then we need to decide what to do with the remaining $n-\ell$ positions to fill, now without having $S_1$. This is hinting dynamic programming! Let $f(i, m)$ be the number of words of length $m$ you can make by using sets $S_i$ through $S_k$. This means the final answer will be $f(1, n)$.

Now, we can use the previous consideration to define a recursive equation for $f$. As we want all possible values of $\ell$, the number of occurrences for a given set, we can just sum over them.

$$ f(i, m) = f(i+1, m) + |S_i|{\sum_{\ell = 1}^m}\binom{m}{\ell}f(i+1, m-\ell) $$

with the base cases being $f(i, 0) = 1$ for all $i$, and $f(k, j) = |S_k|$ for each $1 \leq j \leq m$. Note that $f(i+1, m)$ appears in the sum as we can choose not to use said set at all.

By implementing this recursive equation as a DP you get an algorithm :), maybe there is something even more efficient, but I can't think of anything right now.

$\endgroup$

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.