[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