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

>
> In the problem you describe, what does it mean for the list to be 
> sorted?
>
> Typically, a list is "sorted" when the comparison relation for 
> elements holds for each adjacent pair in the list.  In your problem, 
> it appears to mean something different.
>

You've hit the nail on the head. I've realized that it's fairly trivial 
to modify a simple Bubblesort to provide the old and the new vector and 
the indices of the values to swap, as I intended, but I'm no longer 
sure this is what I really want. Perhaps I'm not looking for a generic 
sorting function at all.

> In fact, my reading of your problem suggests that for many comparison 
> functions, there is no non-exponential search algorithm.  In other 
> words, you have to just "try all the sequences."  Can you narrow down 
> the problem a bit?

The original problem is quite different from the one I gave, I'm 
afraid. I have a list of expressions each consisting of lists of 
arbitrary labels and a payload, and I have a list of 'movement rules' 
formulated by means of the labels. Currently, I think I'd need only two 
such rules: a<b reading "entry with label a is moved before the first 
entry with label b" and "a<+b" reading "a is moved immediately before 
b". (Ideally, these rules would be static linear precedence 
constraints, but I haven't yet figured out how to deal with the 
constraint hierachies I'd need in this case---see second example 
below.)

Problem: given an input list or vector of expressions e and a list of 
constraints c, compute all possible permutations of e that may result 
from applications of the rules in c

Example:  e is ((a 1) (b 2) (a 3)), c is ((< a b))

Solution 1:  ((a 1) (a 3) (b 2))
Solution 2:  ((a 3) (a 1) (b 2))

Example: e is ((a 1) (b 2) (a 3) (b 4) (a 5) (c 6) ((a d) 7)), c is ((< 
a b) (<+ d c))

Solutions: any permutation of thist of a-entries followed by (b 2) (b4) 
(c 6) i.e. the second rule is actually cancelled out by the first one

Example: e is ((a 1) (b 2) (b 3) (a 4)), c is ((<+ a b))

Solution: ((a 1) (b 2) (a 4) (b 3))

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.

Does perhaps someone have an advice on how to tackle this problem?

Best regards,

Erich