Yes. Hmm. Well, you could certainly do a simple enough one like that based on my original idea: if you score x for a deletion or insertion, and y for the interchange of adjacent elements, then it seems clear that the minimum edit distance between two lists is equal to 2x*(number of completely different elements) + y*(number of misordered pairs within the common subset of elements). (Based on the strategy "remove all elements that need to be absent, reorder the common subset, insert all new elements". Any other approach risks using additional interchanges to move things past elements that could instead have been removed beforehand or added afterwards.)
I'd be inclined to arrange that y is proportional to x/(n-1) as n varies, so that no matter what the length of the list you'd score the same fraction of full marks for getting exactly the right list in exactly the wrong order. Then it's just a matter of adjusting the remaining constant factor between x and y, and scaling so that full marks is some sort of nice round number (either a constant or n, as you please).
eta: oh no, I'm wrong again! In fact, my formula above is not quite right, because of the possibility that a single massively misordered element might be more cheaply dealt with as a deletion and insertion than as lots of interchanges to move it to the right place. This only comes into play if the constant factor is such that 2x can ever be less than (n-1)y, but if that's the case then working out the minimum edit distance might get fairly hairy. Perhaps it would be better to treat this as a sanity constraint on the constant factor :-)
no subject
Date: 2008-10-20 04:47 pm (UTC)I'd be inclined to arrange that y is proportional to x/(n-1) as n varies, so that no matter what the length of the list you'd score the same fraction of full marks for getting exactly the right list in exactly the wrong order. Then it's just a matter of adjusting the remaining constant factor between x and y, and scaling so that full marks is some sort of nice round number (either a constant or n, as you please).
eta: oh no, I'm wrong again! In fact, my formula above is not quite right, because of the possibility that a single massively misordered element might be more cheaply dealt with as a deletion and insertion than as lots of interchanges to move it to the right place. This only comes into play if the constant factor is such that 2x can ever be less than (n-1)y, but if that's the case then working out the minimum edit distance might get fairly hairy. Perhaps it would be better to treat this as a sanity constraint on the constant factor :-)