Hi there!
I strongly suspect that 'sort is severely broken. Attached is some code I
wrote to do a Burrows-Wheeler transform. If you don't know what that is,
don't worry - it's a transformation used for compressing text, but that's
irrelevant for this mail. The important part is that in order to do this
transformation, I need to sort a list in a special way.
Try running the program. Four times the line which prints "Not sorted" is
executed. The critical part is this:
; Sort the permutations in lexicographic order
sort/compare permutations :sort-func
; Check if the sorting went well
for i 2 input-length 1 [
if (sort-func pick permutations (i - 1)
pick permutations i) = 1 [
print ["Not sorted:" pick permutations (i - 1) pick permutations i]
]
]
First, I sort the list "permutations", using my own sorting function. This
line _should_ sort "permutations" so that for two neighbouring entries in
"permutations", say entry i and entry i+1, the following expression:
sort-func (pick permutations i) (pick permutations (i + 1))
should in no way give 1. That is, the sorting function taken on any entry and
its rightmost neighbour should give either 0 or -1 (that is, the entry should
be less than or equal to its right neighbour). Right?
Or have I just missed a point in the attached script?
Kind regards,
--
Ole Friis <[EMAIL PROTECTED]>
Amiga is a trademark of Amiga Inc.
REBOL []
input: "this is the" ; 8 10
input-length: length? input
; Burrows-Wheeler transform
; Orders the n1'th and the n2'th permutations of the input
sort-func: func [n1 n2] [
loop input-length [
n1: n1 + 1
n2: n2 + 1
if n1 > input-length [n1: 1]
if n2 > input-length [n2: 1]
c1: pick input n1
c2: pick input n2
if c1 > c2 [return 1]
if c2 > c1 [return -1]
]
return 0
]
; Prints the n'th permutation of the input
print-perm: func [n] [
for i 1 input-length 1 [
n: n + 1
if n > input-length [n: 1]
prin pick input n
]
print ""
]
; Build a representation of the permutations
permutations: make block! input-length
for i 0 (input-length - 1) 1 [append permutations i]
; Sort the permutations in lexicographic order
sort/compare permutations :sort-func
; Check if the sorting went well
for i 2 input-length 1 [
if (sort-func pick permutations (i - 1)
pick permutations i) = 1 [
print ["Not sorted:" pick permutations (i - 1) pick permutations i]
]
]
; Some feedback I like
print permutations
foreach permutation permutations [print-perm permutation]
