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
