Wow, I contradicted myself in my own email. I only really meant the second part, where I said that you don't need to use map-permutation.
Dan On Wed, Feb 25, 2009 at 1:56 PM, Daniel Ehrenberg <[email protected]> wrote: > What you really want to do is calculate the permutation directly, and > then use map-permutation. I suspect the permutation can be calculated > in linear time. Here's a quick O(n log log n) solution, which is > basically as good. (I've never written an algorithm before which came > out with a log log complexity, so this is fun for me!) > > USE: lists > > : evens/odds ( seq -- even odd ) > <enum> >alist [ first even? ] partition [ values ] bi@ ; > > : reorder>list ( seq -- seq-list ) > dup length 2 <= > [ 1list ] > [ evens/odds reorder>list cons ] > if ; > > : reorder ( seq -- newseq ) > reorder>list list>array concat ; > > By the way, there's no particular reason why you need to use > map-permutation for this (unless you're applying the same permutation > several times to sequences of the same length); you can just apply it > directly to your sequence. > > Dan > > On Wed, Feb 25, 2009 at 9:59 AM, Jon Kleiser <[email protected]> wrote: >> Thanks, Jesse! Your solution looks fine. I'll study the words 'keep' and >> 'reduce' so I can understand the magic involved. ;-) >> >> There may be a more direct way to do this. Maybe some recursive method? >> As you may have seen, if the initial sequence is >> { 0 1 2 3 4 5 6 7 8 9 }, then the result will be >> { 0 2 4 6 8 1 5 9 7 3 }. As I'm going to apply the move-core-to-end on >> that, over and over, I could use the first result as a permutation >> sequence with Daniel Ehrenberg's map-permutation word. >> >> /Jon >> >> On 2/25/09 1:11 PM, Jesse Rusak wrote: >>> How about this? >>> >>> : move-core-to-end ( seq -- seq ) >>> [ length 2 - [1,b] ] keep [ swap move-to-end ] reduce ; >>> >>> Though I feel like there's probably a more direct way to do this than >>> moving each element in turn. >>> >>> - Jesse >>> >>> On 25-Feb-09, at 4:30 AM, Jon Kleiser wrote: >>> >>>> Here's follow-up to my first question about how to move the nth >>>> element >>>> to the end, which Daniel and Slava had several solutions for. >>>> >>>> On 2/23/09 7:19 PM, Daniel Ehrenberg wrote: >>>>> Well, here's an inefficient way to do it, but the code is pretty: >>>>> >>>>> : move-to-end ( n seq -- newseq ) >>>>> [ remove-nth ] [ nth ] 2bi suffix ; >>>> I now wanted to apply that operation for n=1 to n=length-2, i.e. >>>> skipping the first (0) and last (length-1) index. I came up with the >>>> following solution, but I suspect Daniel, Slava, or other Factor heads >>>> on this list, may have a better (looking) way of doing it, maybe >>>> without >>>> the variable. Here's mine: >>>> >>>> : move-core-to-end ( seq -- seq ) >>>> SYMBOL: target >>>> dup >>>> target set >>>> length 2 - [1,b] [ target get move-to-end target set ] each >>>> target get ; >>>> >>>> /Jon >> >> ------------------------------------------------------------------------------ >> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA >> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise >> -Strategies to boost innovation and cut costs with open source participation >> -Receive a $600 discount off the registration fee with the source code: SFAD >> http://p.sf.net/sfu/XcvMzF8H >> _______________________________________________ >> Factor-talk mailing list >> [email protected] >> https://lists.sourceforge.net/lists/listinfo/factor-talk >> > ------------------------------------------------------------------------------ Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise -Strategies to boost innovation and cut costs with open source participation -Receive a $600 discount off the registration fee with the source code: SFAD http://p.sf.net/sfu/XcvMzF8H _______________________________________________ Factor-talk mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/factor-talk
