Sorry, I cannot come up with the name of an algorithm or problem for the following algorithm. I will state the problem and then what I have tried and perhaps someone can point me in the right direction.

Imagine you have a bag of items (unordered, duplicates permitted). In practice the bag may contain 2-20 items in case this relaxation helps.

The goal is to find the minimum length chain (ordered link list in case we have different notions of a chain) which contains all of the items in the bag in any order.

A chain consists of a start token (not present in bag) followed by any number of items followed by an end token (also not in bag).

The chain is formed by piecing together n-tuples (order is important) and as a further relaxation let us say the n value is the same for all tuples. In practice, I am working with n = 3. Chains may be "blended" as opposed to concatenated if they have overlapping elements. For example, consider (a,b,c) and (c,d,e). The may be joined as (a,b,c,d,e). Likewise, (a,b,c) and (b,c,d) may be joined as (a,b,c,d). Some tuples may have a start token in the first position and some tokens make have an end token in the last position which of course allows there to be a solution to the problem.

So it would seem to me that an exact solution to the problem is not tractable in general. Some sort of optimization algorithm would be necessary in order to get a "good" solution to the problem. "Good" solutions I can live with.

What I have started with is a greedy approach where on the first pass you find the tuple which contains the most number of elements in the bag, arbitrarily breaking ties. Create a data structure which holds the chain we have built so far, and stick the chosen tuple into this data structure. Split the problem into 2 subproblems, the start token side and the end token side. Until the first token of the data structure of subproblem 1 is a start token and the last token of subproblem 2 is an end token, grow the chain such that we are trying to find the stop condition as soon as possible (start or end token depending on the subproblem) while also trying to exhaust the contents of the bag as soon as possible. This may not be good because each subproblem has to communicate with each other as to how many items are left in the bag which need to be included.

Anyone seen this problem anywhere? Any thoughts as to how to improve (or get to work correctly) this algorithm? This is a real problem I am tackling which is a smart part of a much larger system and is not a toy problem or a homework problem.

**EDIT**

Sorry all I been away from the computer today. I will try to post an example solution which is not too trivial, yet not too intricate to see.

Given:

`Bag = {A, B, C, D}`

(I make it a set for the sake of example, but each item can appear more than once)`/ = Start Token`

`\ = End Token`

3-Tuples (Triples): I label them a-g for simplicity in naming. The lowercase letters have no actual function in the problem.

`(/,A, E) a (/,C, D) b (/,G, H) c (D,B, A) d (C,G, H) e (B,A, \) f (G,H, \) g`

Solution: If we chain together b, d and f we get `(/,C,D,B,A,\)`

.

This is the shortest possible chain containing all elements in the bag which is length 6 if you count both the start and end token. In general, the shortest possible path is of length |BAG| + 2, if it in fact exists. I hope my problem statement makes more sense now.