World: r3wp

I should have a look on your merge implementation.

It's said that "merging" merge with insertion sort give better results

but as it is now, you got pretty nice  results

merging merge with insertion sort give better results

 - actually, it depends; "merging merge with insertion sort" gives 
 worse results from the information-theoretical POV (IMO), since you 
 "prefer certain permutations" (= give them higher probability)

Thus, you can sort certain permutations (the ones already sorted) 
much faster, than is the "information theoretical limit", but at 
the cost of exceeding it noticeably sorting other permutations.

Searching for an optimal (small and fast) implementation of the following 
pattern.
* Swap two subsets inside a serie.

input 
	block:  [4  5  6   1 2] (5 values)
	Starting index of the 2nd subset inside the block: 4

Output:
	[ 1 2    4  5  6] 

Easy to do in plain Rebol right ?

But here's the trouble, It must be memory safe. You're not allowed 
to do any memory allocation.

You're can only swap values inside the block. And the number of swaps 
should be optimal.
(no sort, no parse, no copy/make/insert/append/change)

Don't want something recursive aswell

Just for starters.....This does it with 12 XORs (three per swap).

But the tricky bit may be pre-computing the from-list and to-list 
mapping

;; function to do the swap

swap-items: func [
   data [block!]
   from-list [block!]
   to-list [block!]
   /local
    ind1
    ind2
 ][
 for n 1 length? from-list 1 [
     ind1: from-list/:n
     ind2: to-list/:n
 
     data/:ind1: xor data/:ind1 data/:ind2
     data/:ind2: xor data/:ind1 data/:ind2
     data/:ind1: xor data/:ind1 data/:ind2
     ]
     return data
    ]

;; Sample run    
     block: [4 5 6 1 2]
     probe swap-items block [1 2  1 1] [3 4 5 2]
    [1 2 4 5 6]

I should have said: the values can be of any type,.integers or anything 
else.

You don't need to find a tricky way to swap values. The purpose is 
not to find how to swap values.

The purpose is to find an algorithm with a minimal amount of single 
swaps .
>> swap-sub [a b 1 d  z 3   X 3 Y ]  7 
== [ X 3 Y   a b 1 d z 3]

in R3, you can swap values like this:
swap [a] [b]
in R2
a: also b a: b

Or use a tmp variable, as you want.

Any kind of these methods count as 1 swap.

what does that 7 in swap-sub [a b 1 d  z 3   X 3 Y ]  7 mean?

7 is the index if the second subset in the serie

where X stand

I try to swap [[a b 1 d  z 3]   [X 3 Y ]]
minus the sub blocks

OK, thanks

Not optimal, but a start:


bubble-to-front: funct [series index] [for i index 2 -1 [swap b: 
at series i back b] series]

swap-sub: funct [series position] [loop (n: length? series) - position 
+ 1 [bubble-to-front series n] series]

I've written some very clunky code that I'd be ashamed to post as 
a solution.

But I can offer you an algorithm that acheives the effect in N-1 
swaps at most where 
N is the sum of the lengths of the two sequences.
It's the more-or-less same algorithm used by Andreas.

Here's how it works. Given these two sequences:
       a b c    1 2 3 4 5 6 7

Step1: cyclically rotate the longer sequence M times, where M is 
the difference in length of the sequences. So in this case, we rotate 
3 (7 - 4) times:
       a b c    4 5 6 7    1 2 3


Step2: swap the elements of the shorter sequence with the tail of 
the longer one:
       1 2 3    4 5 6 7    a b c
And it's done.


The cycling in place is the tricky part. It can be done, but my code 
is just too ugly to share :(

Andreas's bubble-to-front is an elegant approach to doing the cycling, 
but is not optimed to reduce the number of steps.

It's a managable sub-problem that is a challenge to solve, so I am 
sure someone can do better than me :)

; helper function:
swap-first: func [
	{swap the first elements of A and B}
	a [series!]
	b [series!]
	/local t
][
	set/any 't first a
	change/only a first b
	change/only b get/any 't
]

; implementation:
swap-sub: func [
	{swap the subseries using the SWAP-FIRST function}
	a [series!]
	b [integer!]
	/local la lb pa pb
][
	pa: a
	la: b - 1
	pb: skip a la
	lb: (length? a) - la
	while [all [la > 0 lb > 0]][
		either la <= lb [
			loop la [
				swap-first pa pb
				pa: next pa
				pb: next pb
			]
			pb: skip pa la
			lb: lb - la
		][
			pa: skip pa la - lb
			loop lb [
				swap-first pa pb
				pa: next pa
				pb: next pb
			]
			pa: skip pa negate la
			la: la - lb
			pb: skip pa la
		]
	]
	a
]

but, I do not have a proof at hand, that it is optimal

I had a similar volume of code, but not nearly as neat, Ladislav.


The problem somehow feels that it ought to have a one-liner solution; 
but the constaints on what can be used in the code make that hard 
to find :)

looks more like rebcode :)

When you take away everything that makes REBOL REBOL, there's not 
much left :)

Steeve also forgot to mention that you're not allowed to use syntax.

:/)

this may look more readable:

; implementation:
swap-n: func [
	{swap n elements}
	a [series!]
	b [series!]
	n [integer!]
][
	loop n [swap-first a b a: next a b: next b]
]

swap-sub: func [
	{swap the subseries using the SWAP-FIRST function}
	a [series!]
	b [integer!]
	/local la lb pa pb
][
	pa: a
	la: b - 1
	pb: skip a la
	lb: (length? a) - la
	while [all [la > 0 lb > 0]][
		either la <= lb [
			swap-n pa pb la
			pb: skip pa la
			lb: lb - la
		][
			pa: skip pa la - lb
			swap-n pa pb lb
			pa: skip pa negate la
			la: la - lb
			pb: skip pa la
		]
	]
	a
]

aha, it is wrong, this way

swap-sub: func [
	{swap the subseries using the SWAP-FIRST function}
	a [series!]
	b [integer!]
	/local la lb pa pb
][
	pa: a
	la: b - 1
	pb: skip a la
	lb: (length? a) - la
	while [all [la > 0 lb > 0]][
		either la <= lb [
			swap-n pa pb la
			pa: pb
			pb: skip pa la
			lb: lb - la
		][
			swap-n skip pa la - lb pb lb
			la: la - lb
			pb: skip pa la
		]
	]
	a
]

swap-first: func [
	{swap the first elements of A and B}
	a [series!]
	b [series!]
	/local t
][
	k: k + 1
	set/any 't first a
	change/only a first b
	change/only b get/any 't
]

k: 0
swap-sub [1 2 3 4 5 6 7 8 9] 7
k ; == 6

So, Sunanda, how many swaps you are getting?

If the two series lengths are L1 and L2, I get L1+L2-1 swaps -- at 
most. But there are exceptions, eg:
    [a b c d   1 2]

Needs only 4 swaps....An any [{L1 // L2) = 0 (L2 // L1) = 0] test 
triggers a shortcut.


However .....I also have some edge-case bugs in my code -- so you 
win!!

/9c=8O%%%%%%%%%%%%%%%%%%%%0P/*****5%('rrrrrrrrbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

OUPS my cat on my keyboard ;-)

:-)

Claude, use the little pencil above the typing area for multi-line 
text. That might reduce accidental sending :-)

Thanks for your hard work.
I didn't read your proposals yet, though.

I think I found the optimal way. As you noticed, it involves modulo 
maths.

swap-sub: func [s pos /local len e sav][
	-- pos
	sav: s
	forever [
		e: skip s pos
		len: length? s
		loop len - pos [swap ++ s ++ e]
		if zero? len // pos [break]
		pos: pos - (len // pos)
	]
	sav
]

Now I will rewrite it, with different input parameters, so that it 
can swap sup-parts of larger series.

That looks good steeve -- short, neat code, looks optimal on the 
swap numbers.
And a completely different algorithm to mine.

The swap numbers may be optimal, but it appears to me than the code 
may be faster.

if one swap the ++ operator with --  in some cases, then one may 
reduce the number of forever loops needed.
But the swap number ober the serie will remain the same.

How to waste his time ? Get ladislav's mergesort working in-place.
--> done

Is it faster that way?

Slower, the algorithm more complex, lot of swap.
If it was compiled, maybe...

I wonder, whether the majority of users prefer POKE to stay as-is, 
or would welcome it to accept any-type DATA argument?

I don't use POKE.. what I remeber.. maybe just in some rare cases.

Steeve, good fun. I came to a swap-sub using modulo as well, but 
it only worked for some series lengths, and I had to sleep before 
figuring out which lengths they were, but they surely included prime 
numbers.

(I used only a single loop). I thought maybe I could detect which 
series lengths could be processed using only a single loop, and other 
cases could be processed using another algorithm.

Steeve, did you finish the swap-sub yet? Curious.

It was already, I just changed the inputs for other purposes.

You said above "so that it can swap sub-parts of larger series". 
Is that what you mean?

yeah, i just had to pass an extra parameter to set the length of 
the added sub-parts, instead of calculate it.
But the algorithm remains the same.

Ok, easy.