Why not have a game that has a tutorial half-way through? Maybe it's teaching you things you already know, maybe very obviously covering things that you had to toil over to work out yourself in the beginning, but the section might still fulfill some artistic purpose.
'Memento' (as in, the film) game. First you see the credits, then fight the final boss, then the final stage, etc. Wait... this was done already, in a way; there was this 'Mario clone', but I forget who made it, or what it was called...
I remember now: it was Hempuli's Jump on Mushrooms (video). It's more 'reverse playback' than 'Memento', though.
I'm not sure what other 'parts' of a game might be treatable in this manner, though. I can't think of any other possibilities for interesting abstraction right now.
I imagine that a linear 2D game's level could be assembled from randomly selected pieces, according to how they fit against each other in the way that two sections of a composition may fit in succession or not. But this is pretty crude, as an extension of your idea.