Given a finite set of words, I wish to to write an algorithm which will create a chain of words, where the tail (last letter) of a word n will be the same as the head (first letter) of word n+1. I assume there can be 0 to n! number of chains, and the length of such chains can be 0 to n.
An algorithm to find the length of the longest chain for a given set of words of size n can be:
- Create all chains (
n!chains) - Check all chains and dispose illegal ones (those in which the tail of at least one word is not equal to the head of the subsequent word)
- Determine length of remaining legal chains
- Find maximum length
First 3 steps can be executed during a single run (i.e. create chain > check it > if legal, determine length), but that would still mean this algorithm will run n! times in worst case.
I wonder if there is a way to calculate the length of the longest chain for a given set of words, without having to check all possible chains in advance.
There certainly is a better way than what you did. For example, for $n=100$, your algorithm cannot be run on any computer smaller than our universe, since you cannot store all $n!$ chains anywhere in memory.
I advise you to improve your algorithm to only create legal chains, which will greatly decrease the work you have to do.