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

 From: Erich Rast (erich at snafu.de) Date: Sun Nov 20 11:36:05 EST 2005 Previous message: [plt-scheme] (Slightly Off) Looking for a Sorting Algorithm Next message: [plt-scheme] (Slightly Off) Looking for a Sorting Algorithm Messages sorted by: [date] [thread] [subject] [author]

```>
> 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

```

 Posted on the users mailing list. Previous message: [plt-scheme] (Slightly Off) Looking for a Sorting Algorithm Next message: [plt-scheme] (Slightly Off) Looking for a Sorting Algorithm Messages sorted by: [date] [thread] [subject] [author]