2
$\begingroup$

I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain sufficient instances of specific orthographic properties (at least 5 2-syllable words, 3 closed syllables, etc.).

I've formalized the problem of generating these word lists as follows:

Given:

  • $ A = \{ p_1, p_2, \dots, p_m\}$, the set of all possible distinct properties
  • $\{ w_1, w_2, \dots, w_n\}$, the set of all possible distinct words
  • $ P_1, P_2, \dots, P_n\ $ corresponding property multisets, such that $P_i$ is the multiset of the non-unique properties $\{ p\ |\ p \in A\} $ in word $w_i$. Thus, if $P_i$ contains $p_j$ with multiplicity $k$, then $w_i$ has $k$ instances of the property $p_j$.
  • A requirements multiset $R = \{ p\ |\ p \in A\} $ of non-unique properties that must appear in the word list

Determine the minimal set of unique words $S=\{ w_a,w_b,\dots \}$ with the property multisets $P_S=\{ P_a,P_b,\dots \}$ such that if the requirements multiset $R$ contains $p_i$ with multiplicity $k$, then the union of the solution words' property multisets $\bigcup P_S$ contains $p_i$ with multiplicity $\geq k$.

One example instance and solution to this problem would be as follows:

Given:

  • $A={p_1, p_2, p_3, p_4}$
  • All possible words $w_1, w_2, w_3$
  • Word property multisets $P_1=\{p_1, p_2, p_2, p_3\}$, $P_2=\{p_2, p_3, p_4\}$, and $P_3=\{p_1, p_1, p_1, p_2\}$
  • Requirements multiset $R=\{p_1, p_1, p_2, p_2, p_3, p_4\}$

Solution:

The set of words $\boxed{S=\{w_2, w_3\}}$, which happen to have the property multisets $P_S=\{P_2, P_3\}=\{\{p_2, p_3, p_4\}, \{p_1, p_1, p_1, p_2\}\}$.

Note that $R$ contains $p_1$ and $p_2$ with multiplicity 2, and $p_3$ and $p_4$ with multiplicity 1. Also note that $\bigcup P_S=\{p_1, p_1, p_1, p_2, p_2, p_3, p_4\}$, and thus $P_S$ always contains at least as many copies of any given property as $R$: $p_1$ with multiplicity $3\geq 2$, $p_2$ with multiplicity $2\geq2$, and $p_3$ and $p_4$ with multiplicity $1\geq1$. $P_S$ therefore satisfies all property requirements in $R$, and thus $S$ represents a word list with all the required properties.

Examining the other possible solutions, we determine that any solution set which satisfies all the property requirements in $R$ must contain at least $w_2$ and $w_3$, and thus $P_S$ is minimal. It is therefore the true solution.

So far I've tried greedily sorting words by most properties satisfied (but found many counterexamples) and I'm currently working on a dynamic programming attempt. I've only taken one semester of algorithms though, and I feel like something similar to this problem would appear in a textbook. Any pointers on creating an algorithm or a reduction to some more common problem (constraint satisfaction?) would be greatly appreciated.

I think this problem is superficially similar to this assignment problem, but I'm not sure if the solution could be adapted. This is also my first post, so feel free to tell me to post this differently/somewhere else!

$\endgroup$
1
  • $\begingroup$ Thanks for your feedback. I've edited the problem statement and added an example. $\endgroup$ Jul 6, 2023 at 12:28

1 Answer 1

1
$\begingroup$

The problem is known as Multi-set Multi-cover problem. Since you are choosing a $P_i$ at most once, you can use the dynamic programming based algorithm given in Section 5 of the paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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