Hmm... graphs are a fundamental tool for most of Computer Science problems (or they're my hammer
)
One possible solution is create a graph where the nodes are the stripe colors and the arcs are the allowed pair combinations. Now the problem is to find the shortest n paths (=number of flags) visiting each node one time at most (i.e using each color zero or one time).
I need to assume that you have a known number of colors and the order matters (i.e. YB is a different flag than BY).
If flags can have 1 stripe (just one color in the whole flag) you start counting the paths of size 1 (will be the number of nodes), otherwise, start with the paths of length 2.
Doesn't seem to be expensive as the number of colors is low, but probably more optimizations can be done (i.e. the longest path from a node will give [sumatory of path length] different flags).
What do you guys think?
(I realized you can repeat colors as long as they're not adjacent... this removes the condition that each vertex must be visited only once at most... doesn't seem to affect the algorithm, though)
[ May 15, 2008: Message edited by: Gabriel Claramunt ]