# Need semi-efficient algorithm for 3-dimensional increasing sequence

I have a set of puzzle challenges for a prototype jigsaw puzzle kit, similar to commercial products offered by Thinkfun and Popular Playthings. I have a candidate list of 300 puzzle challenges and would like to select 40 of them. For each challenge, I have a numerical value that represents the challenge's difficulty, another value that represents the challenge's difficulty after one hint is given, and a third value that represents the challenge's difficulty after a second hint is given.

When I present the puzzles ordered by difficulty, ideally the puzzles should also still have the same relative difficulty after a hint is given. For example, a hard puzzle with one hint should not be easier than an easy puzzle with one hint. If I can select 40 puzzles with that property, then I have the advantage that I can say "for younger children, give two hints for each puzzle" and not have to re-order the puzzle numbers.

I don't really need all subsets of 40 that fit my criteria, just one good one. If I had a list of all subsets, though, I would be able to choose one using more desiderata. For example, I would find one that best clusters into four groups of 10, and then label the challenges "easy", "medium", "hard", and "expert".

I would like to find all subsets of 40 of the points so that no matter which dimension I sort the subset on, the ordering is the same.

In other words, find a subset { P0, P1, P2, ... P39 } so that whenever A < B, X[PA] < X[PB], Y[PA] < Y[PB], and Z[PA] < Z[PB].

I tried a stupid recursive greedy algorithm and it is way too slow.

I eventually got the answer I wanted by a smarter dynamic programming approach.

The insight was to realize that although the nature of my problem didn't allow for a total ordering of all the elements, it did allow for a partial ordering of all the elements. The challenge, then, was to calculate the coverings in that partial order. To do that, I used the following algorithm.

``````for each Point in (all points sorted increasingly by dimension X)
let Coverings[Point] = empty set
let Lowerset[Point] = empty set
let Candidates = {all previous points}
for each PrevPoint in (all previous points sorted decreasingly by dimension X)
if (PrevPoint in Candidates and PrevPoint < Point)
let Lowerset[Point] = union(Lowerset[Point], Lowerset[PrevPoint], PrevPoint)
let Candidates = intersection(Candidates, inverse(Lowerset[PrevPoint]))
endif
end for
end for
``````

Having the lines about Candidates isn't strictly necessary, but it makes the code a bit more efficient by not having to look through the same nodes over and over.

Once I had the set of all coverings, I was then able to send it to Graphviz dot to generate a Hasse diagram for my set.

And by looking at my Hasse diagram, I was quickly able to tell that the diameter of my graph was 40, which is just barely enough to do what I want to do.

P.S. I added a bit more of my code to keep track of the "depth" in which the node appears on the Hasse diagram. With that I was able to generate a simpler diagram that removed all coverings that jump a generation.