2
$\begingroup$

I have a set of letters, and a list of words, and I'd like to find all the possible "sentences" that can be built using the words from the list, while using up all the letters in the process. (A word can be used more than once.) The maximum amount of words in a sentence is also given.

For example, my letters are {"a","a","a"}, and for the sake of simplicity, my words are {"a","aa","aaa"}, and I'm looking for sentences of maximum 3 words (cannot be more in this case anyway).

The order of the words in a sentence doesn't matter, so "a aa", and "aa a" would be considered duplicate sentences, so the output would be the following:

{"a a a", "a aa", "aaa"}

I need an algorithm that finds and lists these sentences (no matter how many there might be) for larger sets. Right now I have 9000 words, and 24 letters. (I know the amount of words is way too much, but let's just disregard that in this case.)

I'm really new to this kind of problem solving, and algorithms in general, so I tried several approaches on my own (and with the help of the internet) with obviously not much success.

The closest I could come up with was the following:

I assigned a prime to each character, and then each word would be the product of them, then considering the letters is together are also a "word", I could find out whether a word was a part of it with congruency, then after dividing the set of letters by word after word would eventually end up being 1, which means, I found a sentence.

So with this in mind, my approach was the following:

I start a sentence with each word, then then I find the next possible words for each one. Then I take all the valid (now 2 word) sentences, and find a next word for each of them as well. And I repeat this until I reached the maximum amount of words I'm looking for.

By "valid" sentences, I mean the ones that can be used in the next iteration, which means that their "letters" are not 1 (in which case no more words can be found, and the sentence is done), and a word was found in the previous iteration, no further validation takes place.

The problem with this is that it takes way too much time to be usable, e.g if I start with 3 words, for finding all the 3 word sentences in the worst case I would have to go through the list of words 3+3^2+3^3 times if I'm not mistaken, but I'm looking for sentences with a maximum of 6 words, and I'm supposed to start with a lot more words. Another problem is that with this approach I end up with duplicatons, and I'd need to filter the result in the end.

Are there any algorithms that are suitable for this kind of problem, or can it even be solved in polynomial time?

Thanks in advance

$\endgroup$
  • $\begingroup$ You're using the words permutations and combinations, but from your usage I'm not sure these words have the same meaning as they do in mathematics. Can you describe your question without using these words? $\endgroup$ – Yuval Filmus Jan 13 '18 at 15:42
  • $\begingroup$ I'm not sure what you're trying to achieve. Are you trying to list permutations of a given finite list? Or are there other conditions for a valid 'sentence'? $\endgroup$ – Discrete lizard Jan 13 '18 at 15:43
  • 1
    $\begingroup$ Here is your question as I understand it. You are given a list of letters, a list of words, and an integer $n$. You want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times). $\endgroup$ – Yuval Filmus Jan 13 '18 at 15:43
  • $\begingroup$ Excuse my poor wording, and/or the misuse of words. Yes, exactly that is what I want indeed, I'll edit the question to change the words that have different meanings than what I initially thought. I wanted to say that "a aa", and "aa a" would be considered duplicates. $\endgroup$ – fecka Jan 13 '18 at 16:07
  • $\begingroup$ Also, I don't do any other validations (yet), I'm just trying to get a grasp of the basic algorithms for now. I updated the post in hope of making it a bit clearer. $\endgroup$ – fecka Jan 13 '18 at 16:22
1
$\begingroup$

Suppose you are working with an alphabet of size $d$. Then each word can be represented as its characteristic vector. A characteristic vector $v \in \mathbb{N}^d$ is a vector, where the $i$th entry counts the number of times the $i$th letter appears in the word. For instance, the word $abbad$ would have characteristic vector $(2,2,0,1)$ if the alphabet is $a,b,c,d$.

As Yuval explains, you want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times).

Looking at characteristic vectors, you can think of the problem as follows: you are given vectors $v_1,\dots,v_k$ (corresponding to the list of words) and a vector $w$ (corresponding to the characteristic vector for the list of letters), and you want to find non-negative integers $a_1,\dots,a_k$ such that

$$a_1 v_1 + \dots + a_k v_k = w.$$

You also want $a_1 + \dots + a_k \le n$ (to satisfy requirement (2) above). You want to enumerate all solutions $a_1,\dots,a_k$ that satisfy these requirements.

This turns out to be an instance of enumerating lattice points in a convex polytope, for which there are well-studied algorithms. See the following paper for an overview:

You could try applying one of those algorithms to your problem to see how well they work.


Alternatively, it's also possible to solve the problem by repeatedly invoking an ILP solver. You can use an ILP solver to test whether any solution exists, and the largest value of $a_1$ such that a solution exists. Then, if at least one solution exists, you enumerate $a_1=0,1,2,\dots$, and for each value of $a_1$, plug in the value of $a_1$ and recursively invoke the same algorithm to enumerate all solutions for $a_2,\dots,a_k$ (such that $a_2 v_2 + \dots + a_k v_k = w - a_1 v_1$ and $a_2 + \dots a_k \le n - a_1$). This might be inefficient, though.

$\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.