Depending on how many paragraphs you have, brute force may work:

• Find all keywords in your document and record the paragraph (perhaps a hash of arrays (HoA) would work for this)
• For each combination of paragraphs, determine if you have all keywords
• If you have all keywords, record the paragraphs necessary
• If the number of paragraphs necessary is less than the current minimum, set the current minimum set to the current set of paragraphs.
• ????
• profit

If the number of paragraphs is very large, the number of combinations may exceed your processing capabilities. Like I said, brute force :-)

Alternate solution

Does this reduce to a form of the spanning tree problem? Perhaps if you would arrange set of graphs with two types of nodes (paragraphs - P, and words - W) where W are adjacent only to the containing P, and P is adjacent only to the W it contains, that you could

• for each graph
• find the minimum depth to touch all W nodes (spanning tree)

The sum of those depths (and the associated P nodes on those paths) should be your ideal list of paragraphs.

I think (still have not had coffee this AM).

Update: Given the updated information on the number of words and paragraphs, spanning tree may not be the best solution. Perhaps I will play with this and see if I can find the time to drop what is in my head down on paper.

Update 2: This algorithm is not suitable for large quantities of P from a big-O standpoint. If I have it right, it comes down to something along the lines of O(W * 2^P). The first pass on each connected graph would need to try all combinations of P, with a maximum depth of W. Perhaps the upper bound can be reduced, but not at my current coffee levels.

P.S. I have had problems this complex for homework. Perhaps not 100 level homework, but these problems do exist in upper level courses, and there are people who try to fake their way even at that level. So please, excuse some cynicism and a lack of desire from some to provide a full solution.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.