[REBOL] Re: sort/scramble
Hi, Anton, Anton Rolls wrote: > > You might be able to do all this in the sort > comparator function somehow, but it's not obvious > to me. > I don't believe that it's possible to handle all of this via SORT/COMPARE . The comparison function only tells whether two values are in order or out of order (presumably the basis for a decision whether to swap them, regardless of sorting strategy: shellsort, quicksort, heapsort, bubblesort, etc.) Exchanging two elements (or partitioning the set) based on a two-element comparison is guaranteed to improve the net "sortedness" of the entire collection, without regard for the rest of the values. (The elements don't even have to be adjacent for this to be true!) The property of a block that says "all pairs of adjacent elements are different" for some definition of "different" is a global property and can't necessarily be improved by considering only two values. If they are the same, then clearly one of them must be swapped away from the other, but without taking more of the collection into account, it is not possible to guarantee that such a swap will improve the desired condition. For example: ... a b c d e f... if the values represented by C and D are "same" for the case at hand, we MIGHT be able to improve things by swapping B and C, but only if A and C differ and B and D differ, etc. I'm not saying that one couldn't create an tuned algorithm to massage the collection into the desired state, only that I don't believe there's a way to do it with a sorting function. -jn- -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Hallvard, what a curious problem? Why? I think the way to go is using the sort comparator function as I showed before. The two elements to be compared at each step are put into the arguments, here, 'a and 'b. sort/compare blk func [a b][either a/4/3 = #"c" [1][-1]] This moves blocks with the third character of the string equalling character #"c" nextward, and others backward. So after that you are guaranteed all the "c" elements are at the end. Next, I think you should write a loop, that redistributes these "c" blocks amongst the others as best it can. So the final result might look like [c n c n c n c n n n n ...] (Where c = "c"-blocks, and n = non-"c" blocks) You might be able to do all this in the sort comparator function somehow, but it's not obvious to me. How much does speed matter? Anton. > Dixit Joel Neely (03.06 04.01.2004): > >How about this: > > > > >> random [0 1 2 3 4 5 6 7 8 9] > > == [8 9 3 4 2 1 7 6 0 5] > > Ah, of course. I didn't think about the fact that 'random takes > anything as an argument... > > >Can you provide a little more detail on your requirements? > > Yes. Especially since I have nested blocks. I have a block with, > say 10 blocks inside it. Each block has many different data types > within it (but only one element matters). I want to unsort them > so that _part of_ the fourth element (a string) is not identical > in adjacent blocks. So this is what I want to avoid (not real example): > > example: [[4 1 7 "nicsrg" 5 6 3 8 2 9] [3 1 2 "sicrtg" 9 8 4 7 6 > 5] [9 3 7 "iscgtn" 6 2 8 5 4 1] [1 3 8 "inctrg" 5 2 9 4 6 7] [9 6 > 5 "ngsirt" 8 2 1 3 7 4] [3 7 8 "igtnrs" 4 1 2 9 5 6] [6 4 8 > "gnrsit" 2 3 9 1 5 7] [9 5 4 "sntgir" 6 7 8 2 1 3] [6 7 4 > "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4]] > > In the first four blocks, the third character in the fourth > element is #"c". I want these four blocks split apart. Getting at > the character in question is easy (foreach b example [print pick > fourth b 3]), but unsorting the blocks from there? > > Any help appreciated > HY -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Also check refinements of random to make it more random. By the way, this is what I actually meant: sort/compare blk func [a b][(random 3) - 2] Anton. > Try this on: > > sort/compare blk func [a b][(random 2) - 1] > > Anton. > > > Hi > > > > I need a function that will make sure a block is _not_ sorted. > > > > ex: > > >> sort/scramble [ 1 2 7 7 7 4 9 f 3 h h h h 3e 54 5 4 k] > > >> [ 1 h 2 7 h 4 9 f 3 h 7 3e 54 7 h 5 4 k] > > > > Is this feasible without a lot of work? Would anyone happen to > > have such a function in a drawer somewhere? > > > > Thanks, > > HY > > > > Prætera censeo esse delendam -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Dixit Joel Neely (00.11 05.01.2004): >[...] >adjacent elements are now different. Finally, for your example: > > example: [[4 1 7 "nicsrg" 5 6 3 8 2 9] [3 1 2 "sicrtg" 9 8 4 7 6 5] > [9 3 7 "iscgtn" 6 2 8 5 4 1] [1 3 8 "inctrg" 5 2 9 4 6 7] > [9 6 5 "ngsirt" 8 2 1 3 7 4] [3 7 8 "igtnrs" 4 1 2 9 5 6] > [6 4 8 "gnrsit" 2 3 9 1 5 7] [9 5 4 "sntgir" 6 7 8 2 1 3] > [6 7 4 "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4]] > example: riffle sort/compare example func [a b][a/4/3 < b/4/3] > foreach item example [print mold item] > >which gives: > > [6 4 8 "gnrsit" 2 3 9 1 5 7] > [1 3 8 "inctrg" 5 2 9 4 6 7] > [9 6 5 "ngsirt" 8 2 1 3 7 4] > [3 1 2 "sicrtg" 9 8 4 7 6 5] > [3 7 8 "igtnrs" 4 1 2 9 5 6] > [4 1 7 "nicsrg" 5 6 3 8 2 9] > [6 7 4 "gstinr" 1 5 2 3 9 8] > [7 9 2 "sgcnit" 5 1 8 3 6 4] > [9 5 4 "sntgir" 6 7 8 2 1 3] > [9 3 7 "iscgtn" 6 2 8 5 4 1] > >where adjacent (sub-)blocks differ in the third character of the >fourth element. And whereby my problem seems to be solved. Thanks, Joel! HY Prætera censeo Carthaginem esse delendam -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Hi, Hallvard, To ensure "unsorted", first sort, then interleave second and first halves. (Assuming you have enough distinct values that moving halfway through the sorted order gives you a different value.) Hallvard Ystad wrote: > > I have a block with, say 10 blocks inside it. Each block has many > different data types within it (but only one element matters). > I want to unsort them so that _part of_ the fourth element (a > string) is not identical in adjacent blocks... > > example: [[4 1 7 "nicsrg" 5 6 3 8 2 9] [3 1 2 "sicrtg" 9 8 4 7 6 5] > [9 3 7 "iscgtn" 6 2 8 5 4 1] [1 3 8 "inctrg" 5 2 9 4 6 7] > [9 6 5 "ngsirt" 8 2 1 3 7 4] [3 7 8 "igtnrs" 4 1 2 9 5 6] > [6 4 8 "gnrsit" 2 3 9 1 5 7] [9 5 4 "sntgir" 6 7 8 2 1 3] > [6 7 4 "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4]] > > In the first four blocks, the third character in the fourth element > is #"c". I want these four blocks split apart. Getting at the > character in question is easy (foreach b example [print pick fourth > b 3]), but unsorting the blocks from there? > Let's define (and demonstrate) the interleaving function first: riffle: func [b [block!] /local n j result] [ j: to-integer (n: length? b) / 2 result: make block! n for i 1 j 1 [ append/only result pick b i + j append/only result pick b i ] if odd? n [append/only result last b] result ] Which behaves as: >> riffle [0 1 2 3 4 5 6 7 8 9] == [5 0 6 1 7 2 8 3 9 4] >> riffle [0 1 2 3 4 5 6 7 8] == [4 0 5 1 6 2 7 3 8] So that (for a trivial case, which I know is already sorted) >> riffle sort [0 0 0 1 1 1 2 2 2 3 3 3] == [2 0 2 0 2 0 3 1 3 1 3 1] adjacent elements are now different. Finally, for your example: example: [[4 1 7 "nicsrg" 5 6 3 8 2 9] [3 1 2 "sicrtg" 9 8 4 7 6 5] [9 3 7 "iscgtn" 6 2 8 5 4 1] [1 3 8 "inctrg" 5 2 9 4 6 7] [9 6 5 "ngsirt" 8 2 1 3 7 4] [3 7 8 "igtnrs" 4 1 2 9 5 6] [6 4 8 "gnrsit" 2 3 9 1 5 7] [9 5 4 "sntgir" 6 7 8 2 1 3] [6 7 4 "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4]] example: riffle sort/compare example func [a b][a/4/3 < b/4/3] foreach item example [print mold item] which gives: [6 4 8 "gnrsit" 2 3 9 1 5 7] [1 3 8 "inctrg" 5 2 9 4 6 7] [9 6 5 "ngsirt" 8 2 1 3 7 4] [3 1 2 "sicrtg" 9 8 4 7 6 5] [3 7 8 "igtnrs" 4 1 2 9 5 6] [4 1 7 "nicsrg" 5 6 3 8 2 9] [6 7 4 "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4] [9 5 4 "sntgir" 6 7 8 2 1 3] [9 3 7 "iscgtn" 6 2 8 5 4 1] where adjacent (sub-)blocks differ in the third character of the fourth element. -jn- -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Dixit Joel Neely (03.06 04.01.2004): >How about this: > > >> random [0 1 2 3 4 5 6 7 8 9] > == [8 9 3 4 2 1 7 6 0 5] Ah, of course. I didn't think about the fact that 'random takes anything as an argument... >Can you provide a little more detail on your requirements? Yes. Especially since I have nested blocks. I have a block with, say 10 blocks inside it. Each block has many different data types within it (but only one element matters). I want to unsort them so that _part of_ the fourth element (a string) is not identical in adjacent blocks. So this is what I want to avoid (not real example): example: [[4 1 7 "nicsrg" 5 6 3 8 2 9] [3 1 2 "sicrtg" 9 8 4 7 6 5] [9 3 7 "iscgtn" 6 2 8 5 4 1] [1 3 8 "inctrg" 5 2 9 4 6 7] [9 6 5 "ngsirt" 8 2 1 3 7 4] [3 7 8 "igtnrs" 4 1 2 9 5 6] [6 4 8 "gnrsit" 2 3 9 1 5 7] [9 5 4 "sntgir" 6 7 8 2 1 3] [6 7 4 "gstinr" 1 5 2 3 9 8] [7 9 2 "sgcnit" 5 1 8 3 6 4]] In the first four blocks, the third character in the fourth element is #"c". I want these four blocks split apart. Getting at the character in question is easy (foreach b example [print pick fourth b 3]), but unsorting the blocks from there? Any help appreciated HY >-jn- > > >-- >To unsubscribe from this list, just send an email to >[EMAIL PROTECTED] with unsubscribe as the subject. Prætera censeo Carthaginem esse delendam -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
> Is this feasible without a lot of work? Would anyone happen to have such a function in a drawer somewhere? 'random seems to work OK for me: >> random [ 1 2 7 7 7 4 9 f 3 h h h h 3 54 5 4 k] == [4 3 7 k 7 h 2 54 7 4 h 9 1 3 h f h 5] (Once I changed that '3e to something that Rebol could accept.) Andrew J Martin Speaking in tongues and performing miracles. ICQ: 26227169 http://www.rebol.it/Valley/ http://valley.orcon.net.nz/ http://Valley.150m.com/ -><- -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Hi, Hallvard, Hallvard Ystad wrote: > Hi > > I need a function that will make sure a block is _not_ sorted. > How about this: >> random [0 1 2 3 4 5 6 7 8 9] == [8 9 3 4 2 1 7 6 0 5] Of course, there's a 1 in 3628800 chance that a random arrangement of ten values will actually be in order! ;-) If you really mean *NOT* sorted (and your values are distinct), but don't care about randomness, then reverse sort foo will make sure that FOO is _not_ sorted in ascending order. Can you provide a little more detail on your requirements? -jn- -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
On 04-Jan-04, Hallvard Ystad wrote: > Hi > I need a function that will make sure a block is _not_ sorted. > ex: >>> sort/scramble [ 1 2 7 7 7 4 9 f 3 h h h h 3e 54 5 4 k] >>> [ 1 h 2 7 h 4 9 f 3 h 7 3e 54 7 h 5 4 k] Is that a real, in-use block? As I get an error with it... >> blk: [ 1 2 7 7 7 4 9 f 3 h h h h 3e 54 5 4 k] ** Syntax Error: Invalid decimal -- 3e ** Near: (line 1) [ 1 2 7 7 7 4 9 f 3 h h h h 3e 54 5 4 k] > Is this feasible without a lot of work? Would anyone happen to have > such a function in a drawer somewhere? RANDOM can be used directly on blocks (and series). ie... >> random [ 1 2 7 7 7 4 9 f 3 h h h h 3 e 54 5 4 k] == [3 1 4 7 7 h h 5 3 h 2 7 54 k e f 9 4 h] >> random [ 1 2 7 7 7 4 9 f 3 h h h h 3 e 54 5 4 k] == [3 h 7 4 h 54 4 5 1 2 e 7 k h h 7 9 3 f] >> random [ 1 2 7 7 7 4 9 f 3 h h h h 3 e 54 5 4 k] == [9 4 h 5 3 4 7 2 7 7 3 h f 1 54 h e h k] It just depends on how you define unsorted... -- Carl Read -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
[REBOL] Re: sort/scramble
Try this on: sort/compare blk func [a b][(random 2) - 1] Anton. > Hi > > I need a function that will make sure a block is _not_ sorted. > > ex: > >> sort/scramble [ 1 2 7 7 7 4 9 f 3 h h h h 3e 54 5 4 k] > >> [ 1 h 2 7 h 4 9 f 3 h 7 3e 54 7 h 5 4 k] > > Is this feasible without a lot of work? Would anyone happen to > have such a function in a drawer somewhere? > > Thanks, > HY > > Prætera censeo esse delendam -- To unsubscribe from this list, just send an email to [EMAIL PROTECTED] with unsubscribe as the subject.
