[plt-scheme] (Slightly Off) Looking for a Sorting Algorithm

On Sun, 2005-11-20 at 17:36 +0100, Erich Rast wrote:
   . . .
> My original idea was to first sort the list such that it satisfies the 
> rules, i.e. get one solution, and then determine the sublists that can 
> be permuted without violating a rule and permute these lists whenever 
> an output is needed. But by now I believe using a generic search 
> algorithm won't help much.

Perhaps a topological sort could be used to provide the first
permutation that satisfies the rules, followed by a backtracking
algorithm working off that first permutation to generate the remaining
permutations.

It does appear that "x < y" rules define something close to a partial
order on labels, which is the hallmark of topological sort.

 -- Bill Wood