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

On Nov 20, 2005, at 8:36 AM, Erich Rast wrote:

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

Your problem still doesn't make complete sense to me.

1) does the initial ordering of the elements affect the set of legal  
solutions?
2) in your second example you have ... (c 6) ((a d) 7).... That is,  
some of the elements have a symbol, and some have a list of symbols.   
Is (c 6) an abbreviation for ((c) 6) ?
3) your use of the word "moved" in the <+ definition is worrisome.   
Do you mean simply that "a must occur immediately before b"?  Also,  
in the presence of multiple 'a' labels, what does this mean?  Your  
third example would seem to suggest that it means "every element  
containing an 'a' label must be followed by an element with a 'b'  
label.  Is this correct?
4) along the same lines, does (< a b) mean that all a's must occur  
before all b's, or that every a must occur before a b?

John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2430 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20051120/f57f9f33/attachment.p7s>