"Interleave" permutation algorithm?
mike3
Is there a fast algorithm to compute the "interleave" and
"deinterleave" permutation of any even-number-length data in-place?
Like this:
0123456789
becomes
0516273849
(interleave)
and
0516273849
becomes
0123456789
(deinterleave)
That is, the "interleave" permutation takes the two halves of the
sequence and interleaves them together, while the "deinterleave" does
the opposite.
Sjouke Burry
loop:adr=(adr+6)%10;
out(adr)=in(i);
i++;
until i==10;
Richard Heathfield
> mike3 wrote:
>> Hi.
>>
>> Is there a fast algorithm to compute the "interleave" and
>> "deinterleave" permutation of any even-number-length data in-place?
<snip>
> Step through the string with: i=0,ard=0;
> loop:adr=(adr+6)%10;
> out(adr)=in(i);
> i++;
> until i==10;
How is that "in-place"?
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
This line unintentionally left unblank
mike3
wrote:
Is this an in-place method? As I wanted an in-place algorithm.
Pascal J. Bourguignon
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length data in-place?
Yes. Any in place permutation can be implemented in O(1) space and
O(n) time, n being the length of the sequence.
--
__Pascal Bourguignon__
mike3
wrote:
> mike3 <mike4...@yahoo.com> writes:
> > Is there a fast algorithm to compute the "interleave" and
> > "deinterleave" permutation of any even-number-length data in-place?
>
> Yes. Any in place permutation can be implemented in O(1) space and
> O(n) time, n being the length of the sequence.
>
So what would be a good in-place algorithm for this permutation?
robert...@yahoo.com
One way:
e = 2; // Start with the first out of place element (the second)
t = element[e];
Loop:
compute e2 = where element[e] *should* go
if e == e2 then element[e2] = t, done
swap t, element[e2]
e = e2;
That generalizes to general reordering if you search through the array
looking for out of place elements, rather than just assuming it's only
one group starting with the second element.
mike3
It might work, but I was wondering if perhaps there might be some
algorithm more specific to this particular permutation.
Willem
) One way:
)
) e = 2; // Start with the first out of place element (the second)
) t = element[e];
) Loop:
) compute e2 = where element[e] *should* go
) if e == e2 then element[e2] = t, done
) swap t, element[e2]
) e = e2;
)
)
) That generalizes to general reordering if you search through the array
) looking for out of place elements, rather than just assuming it's only
) one group starting with the second element.
You'll have to generalize then, because the permutation the OP wants
is not comprised of a single group.
(In the case of 0123456789, the 3 and 6 are exchanged for example.)
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
bartc
One must exist because it's possible to do this with a row of playing cards
1 to 10.
Trying to turn this into an algorithm only gave me a headache however.
But, is it allowed to have an array of marker bits corresponding to each
element?
--
Bartc
Richard Heathfield
> Hi.
>
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length data in-place?
> Like this:
>
> 0123456789
> becomes
> 0516273849
> (interleave)
I won't pretend to have an algorithm for you, but I do have a
suggestion as to how you might break the problem down a bit.
Firstly, identify how many "rings" there are in the data set. In your
example, there are four: 0 -> 0 (nice and short), 9 -> 9 (that one's
fine), 3 -> 6 -> 3, and 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1.
That's the tricky bit (programmatically speaking, although it's easy
by eye). The next bit is trivial: deal with one ring at a time, using
the standard swap, temp = x, x = y, y = temp (extending as necessary
for the length of the ring). Rings with only one element can of
course be ignored.
De-interleaving can be done similarly.
So the hard bit is identifying the rings without using O(n) space. Any
ideas, folks?
Pascal J. Bourguignon
;; A good one, but not the best:
#+emacs (require 'cl)
(defun interleave (vector)
(flet ((swap (i j) (rotatef (elt vector i) (elt vector j))))
(swap 1 5) ; (0 1 2 3 4 5 6 7 8 9)
(swap 2 5) ; (0 5 2 3 4 1 6 7 8 9)
(swap 3 6) ; (0 5 1 3 4 2 6 7 8 9)
(swap 4 5) ; (0 5 1 6 2 4 3 7 8 9)
(swap 5 7) ; (0 5 1 6 2 7 3 4 8 9)
(swap 7 8) ; (0 5 1 6 2 7 3 8 4 9)
vector))
(let ((v (vector 0 1 2 3 4 5 6 7 8 9)))
(interleave v)
v)
[0 5 1 6 2 7 3 8 4 9]
(Notice that deinterleave is the same with the order of swaps reversed,
(swap 7 8) first and (swap 1 5) last).
Of course, the question is to generate this sequence of swap for any
even length of vector. And we can optimize the shuffling, by
processing the vector cycle by cycle and avoiding storing moving
values in the vector.
I'll give the answer this evening. ;-)
--
__Pascal Bourguignon__
rossum
wrote:
For a list of size N (N even) then using a zero based, C-style)
numbering we have:
For the element at position p, the new position p' is given by:
if (p < N/2) then p' = 2 * p
if (p >= N/2) then p' = (2 * p) - (N - 1)
rossum
bartc
"bartc" <ba...@freeuk.com> wrote in message
news:tG7lm.72160$OO7....@text.news.virginmedia.com...
A version using an array of marker bytes looks like the following. However
searching for the next un-moved element may slow things down:
a:=(10,20,30,40,50, 60,70,80,90,100)
mark:=(0,)*a.upb
m:=a.upb % 2 #ie. 5
println "Original =",A
do
for i:=1 to a.upb do
if not mark[i] then
x:=a[i]
starti:=i
do
j:=(i<=m | i*2-1 | (i-m)*2)
if j=starti then
a[starti]:=x
mark[starti]:=1
exit
fi
x swap a[j]
mark[j]:=1
i:=j
end
exit
fi
else #python-style for-loop normal exit
exit 2
end
end
println "Interleaved =",A
--
bartc
rossum
<r...@see.sig.invalid> wrote:
>mike3 said:
>
>> Hi.
>>
>> Is there a fast algorithm to compute the "interleave" and
>> "deinterleave" permutation of any even-number-length data in-place?
>> Like this:
>>
>> 0123456789
>> becomes
>> 0516273849
>> (interleave)
>
>I won't pretend to have an algorithm for you, but I do have a
>suggestion as to how you might break the problem down a bit.
>
>Firstly, identify how many "rings" there are in the data set. In your
>example, there are four: 0 -> 0 (nice and short), 9 -> 9 (that one's
>fine), 3 -> 6 -> 3, and 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1.
>
>That's the tricky bit (programmatically speaking, although it's easy
>by eye). The next bit is trivial: deal with one ring at a time, using
>the standard swap, temp = x, x = y, y = temp (extending as necessary
>for the length of the ring). Rings with only one element can of
>course be ignored.
>
>De-interleaving can be done similarly.
>
>So the hard bit is identifying the rings without using O(n) space. Any
>ideas, folks?
Crude, but it works:
while (at least one entry is out of place) do
process the ring that includes that entry
endwhile
Once you know one entry in a ring you can calculate where that entry
should go, and hence the next member of the ring. Follow the ring
until you get back to where you started.
rossum
Moi
> On Tue, 25 Aug 2009 22:26:15 -0700 (PDT), mike3 <mike...@yahoo.com>
> wrote:
>
>>On Aug 25, 9:01 pm, "robertwess...@yahoo.com" <robertwess...@yahoo.com>
>>wrote:
>>> On Aug 25, 9:07 pm, mike3 <mike4...@yahoo.com> wrote:
>>>
>>> > On Aug 25, 8:00 pm, p...@informatimago.com (Pascal J. Bourguignon)
>>> > wrote:
>>>
>>> > > mike3 <mike4...@yahoo.com> writes:
>>> > > > Is there a fast algorithm to compute the "interleave" and
>>> > > > "deinterleave" permutation of any even-number-length data
>>> > > > in-place?
>>>
>>> > > Yes. Any in place permutation can be implemented in O(1) space
>>> > > and O(n) time, n being the length of the sequence.
>>>
> For a list of size N (N even) then using a zero based, C-style)
> numbering we have:
>
> For the element at position p, the new position p' is given by:
> if (p < N/2) then p' = 2 * p
> if (p >= N/2) then p' = (2 * p) - (N - 1)
>
> rossum
Exactly. I had
#include <stdio.h>
#define SPLIT 5
#define TARGET_INDEX(i) (2*((i)%SPLIT)) + (((i)<SPLIT) ? 0 : 1)
int main(int argc, char **argv)
{
int pos=0;
for(pos=0; pos < 10; pos++) {
fprintf(stdout, "%d -->> %d\n", pos, TARGET_INDEX(pos) );
}
return 0;
}
, where SPLIT =(N/2), of course.
BTW: the interleave operation has been suggested as a new hardware CPU
instruction, to implement Morton-addressing for use in matrix-operations.
AvK
Pascal J. Bourguignon
> ;; A good one, but not the best:
> #+emacs (require 'cl)
>
> (defun interleave (vector)
> (flet ((swap (i j) (rotatef (elt vector i) (elt vector j))))
> (swap 1 5) ; (0 1 2 3 4 5 6 7 8 9)
> (swap 2 5) ; (0 5 2 3 4 1 6 7 8 9)
> (swap 3 6) ; (0 5 1 3 4 2 6 7 8 9)
> (swap 4 5) ; (0 5 1 6 2 4 3 7 8 9)
> (swap 5 7) ; (0 5 1 6 2 7 3 4 8 9)
> (swap 7 8) ; (0 5 1 6 2 7 3 8 4 9)
> vector))
>
> (let ((v (vector 0 1 2 3 4 5 6 7 8 9)))
> (interleave v)
> v)
> [0 5 1 6 2 7 3 8 4 9]
>
> (Notice that deinterleave is the same with the order of swaps reversed,
> (swap 7 8) first and (swap 1 5) last).
>
>
> Of course, the question is to generate this sequence of swap for any
> even length of vector. And we can optimize the shuffling, by
> processing the vector cycle by cycle and avoiding storing moving
> values in the vector.
>
> I'll give the answer this evening. ;-)
Ok, here is the answer. (An interesting problem can't wait).
;;; Common Lisp code follows. If you want to try it out, you can
;;; download any Common Lisp implementation, such as
;;; http://clisp.cons.org http://sbcl.sf.net etc.
;;; Three-semicolon comments are explainations, Two-semicolon comments
;;; are examples. The results are after the --> arrow. To try the
;;; example at the REPL (interactive loop), just remove the
;;; semi-colons prefixing the expressions.
;;; IOTA is used only to generate use cases.
(defun iota (count &optional start step)
"
RETURN: A list containing the elements
(start start+step ... start+(count-1)*step)
The start and step parameters default to 0 and 1, respectively.
This procedure takes its name from the APL primitive.
EXAMPLES: (iota 5) => (0 1 2 3 4)
(iota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4)
"
(setf start (or start 0) step (or step 1))
(when (< 0 count)
(do ((result '())
(item (+ start (* step (1- count))) (- item step)))
((< item start) result)
(push item result))))
;;; Most of the following code is meta programming. That is, the
;;; complexities of the algorithms don't matter at run-time, only when
;;; the wanted interleave and deinterleave algorithms are generated.
;;; We will build the INTERLEAVE-PERMUTATION of (iota n) to find in it
;;; the cycles. This is done in O(n).
;; (0 1 2 3 4 5 6 7 8 9)
;; (0 1 2 3 4 )
;; ( 5 6 7 8 9)
;; (0 1 2 3 4 )
;; ( 5 6 7 8 9)
;; (0 5 1 6 2 7 3 8 4 9)
(defun interleave-permutation (length)
"Returns the interleave permutation of the vector (iota length)."
(assert (evenp length))
(coerce (loop
:for l :from 0 :below (/ length 2)
:for r :from (/ length 2)
:collect l :collect r) 'vector))
;; (interleave-permutation 20)
;; --> #(0 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19)
;;; PERMUTATION-CYCLES will find the cycles of any permutation of
;;; (iota n). This is done in O(n): we visit each slot of the vector
;;; once, marking it visited, and following the cycles.
(defun permutation-cycles (permutation)
"
PERMUTATION: A permutation of (iota (length permutation))
RETURN: A list of cycles in the permutation.
Each cycle is represented by an open path of the cycle
The order of the cycles is unspecified.
The starting element of the cycles is unspecified.
The meaning of (a0... ai aj ... an) is that
the aith element goes to the ajth position, and
the anth element goes to the a0th position.
EXAMPLE: (permutation-cycles #(1 2 3 0 4 6 7 8 5))
--> ((0 1 2 3) (4) (5 6 7 8))
"
(loop
:with cycles = '()
:with walked = (make-array (length permutation) :initial-element nil)
:for i :from 0 :below (length permutation)
:do (unless (aref walked i)
(loop
:with cycle = '()
:for k = i :then (elt permutation k)
:until (aref walked k)
:do (push k cycle) (setf (aref walked k) t)
:finally (push cycle cycles)))
:finally (return cycles)))
;; (values (iota 16) (interleave-permutation 16) (permutation-cycles (interleave-permutation 16)))
;; -->
;; (00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15)
;; #(00 08 01 09 02 10 03 11 04 12 05 13 06 14 07 15)
;; ((15) (14 13 11 07) (10 05) (06 12 09 03) (02 04 08 01) (00))
;;; Now that we have cycles, we can generate the rotation of the
;;; elements in the cycle. In Common Lisp we have a ROTATEF operator
;;; that could be used to do it in one step. It is used here only for
;;; two elements (reducing to a swap operation), so you can easily
;;; transpose the algorithm to other programming languages lacking a
;;; variable arity ROTATEF operator.
;;;
;;; We use two temporaries so we can generate reading and writing each
;;; slot only once. GENERATE-CYCLE-SWAPS itself is O(n), n being the
;;; length of the cycle.
;;;
;;; Notice that in the code generated, there is only O(n) operations
;;; (at most one read and one write for each slot of the vector, n
;;; being the length of the vector.
(defun generate-cycle-swaps (cycle vector-name)
"
CYCLE: A list of positions.
The meaning of (a0... ai aj ... an) is that
the aith element goes to the ajth position, and
the anth element goes to the a0th position.
RETURN: Code implementing the permutation corresponding to the
cycle shifting.
"
(case (length cycle)
((0 1) '(progn)) ; nothing to do.
((2) `(rotatef (elt ,vector-name ,(first cycle))
(elt ,vector-name ,(second cycle))))
(otherwise
`(let ((t1 (elt ,vector-name ,(first cycle)))
t2)
,@(loop
:for step :from 0
:for j :in (rest cycle)
:collect (if (evenp step)
`(setf t2 (elt ,vector-name ,j)
(elt ,vector-name ,j) t1)
`(setf t1 (elt ,vector-name ,j)
(elt ,vector-name ,j) t2)) :into expressions
:finally (return (append expressions
(list (if (evenp step)
`(setf (elt ,vector-name ,(first cycle)) t1)
`(setf (elt ,vector-name ,(first cycle)) t2))))))))))
;; (setf *print-circle* nil
;; *PRINT-PRETTY* t)
;;
;; (mapcar (lambda (cycle) (generate-cycle-swaps cycle 'vector))
;; (permutation-cycles (interleave-permutation 16)))
;; -->
;; ((PROGN)
;; (LET ((T1 (ELT VECTOR 14)) T2)
;; (SETF T2 (ELT VECTOR 13) (ELT VECTOR 13) T1)
;; (SETF T1 (ELT VECTOR 11) (ELT VECTOR 11) T2)
;; (SETF T2 (ELT VECTOR 7) (ELT VECTOR 7) T1)
;; (SETF (ELT VECTOR 14) T2))
;; (ROTATEF (ELT VECTOR 10) (ELT VECTOR 5))
;; (LET ((T1 (ELT VECTOR 6)) T2)
;; (SETF T2 (ELT VECTOR 12) (ELT VECTOR 12) T1)
;; (SETF T1 (ELT VECTOR 9) (ELT VECTOR 9) T2)
;; (SETF T2 (ELT VECTOR 3) (ELT VECTOR 3) T1)
;; (SETF (ELT VECTOR 6) T2))
;; (LET ((T1 (ELT VECTOR 2)) T2)
;; (SETF T2 (ELT VECTOR 4) (ELT VECTOR 4) T1)
;; (SETF T1 (ELT VECTOR 8) (ELT VECTOR 8) T2)
;; (SETF T2 (ELT VECTOR 1) (ELT VECTOR 1) T1)
;; (SETF (ELT VECTOR 2) T2))
;; (PROGN))
;;; Now we can generate the interleave and deinterleave functions. We
;;; just wrap calls to the GENERATE-CYCLE-SWAPS function for each
;;; cycle in a function.
;;;
;;; For deinterleave, we reverse the order of each cycle.
;;;
;;; Since the function called are all O(n), and the loop (hidden in
;;; MAPCAR) covers different ranges of the input, these generations
;;; are done in O(n) (n being the LENGTH parameter).
(defun generate-interleave (name length)
(assert (and (not (minusp length)) (evenp length)))
`(defun ,name (vector)
(assert (= ,length (length vector)))
,@(mapcar (lambda (cycle) (generate-cycle-swaps cycle 'vector))
(permutation-cycles (interleave-permutation length)))
vector))
(defun generate-deinterleave (name length)
(assert (and (not (minusp length)) (evenp length)))
`(defun ,name (vector)
(assert (= ,length (length vector)))
,@(mapcar (lambda (cycle) (generate-cycle-swaps (reverse cycle) 'vector))
(permutation-cycles (interleave-permutation length)))
vector))
;;; Finally we define a macro to define these couple of functions easily.
;;; In another programming language, you would just use the equivalent
;;; of the above function to generate a source file, and feed it to
;;; your compiler.
(defmacro define-interleave-functions (interleave-name deinterleave-name length)
`(values
,(generate-interleave interleave-name length)
,(generate-deinterleave deinterleave-name length)))
;; (generate-interleave 'interleave-16 16)
;; -->
;; (DEFUN INTERLEAVE-16 (VECTOR)
;; (ASSERT (= 16 (LENGTH VECTOR)))
;; (PROGN)
;; (LET ((T1 (ELT VECTOR 14)) T2)
;; (SETF T2 (ELT VECTOR 13) (ELT VECTOR 13) T1)
;; (SETF T1 (ELT VECTOR 11) (ELT VECTOR 11) T2)
;; (SETF T2 (ELT VECTOR 7) (ELT VECTOR 7) T1)
;; (SETF (ELT VECTOR 14) T2))
;; (ROTATEF (ELT VECTOR 10) (ELT VECTOR 5))
;; (LET ((T1 (ELT VECTOR 6)) T2)
;; (SETF T2 (ELT VECTOR 12) (ELT VECTOR 12) T1)
;; (SETF T1 (ELT VECTOR 9) (ELT VECTOR 9) T2)
;; (SETF T2 (ELT VECTOR 3) (ELT VECTOR 3) T1)
;; (SETF (ELT VECTOR 6) T2))
;; (LET ((T1 (ELT VECTOR 2)) T2)
;; (SETF T2 (ELT VECTOR 4) (ELT VECTOR 4) T1)
;; (SETF T1 (ELT VECTOR 8) (ELT VECTOR 8) T2)
;; (SETF T2 (ELT VECTOR 1) (ELT VECTOR 1) T1)
;; (SETF (ELT VECTOR 2) T2))
;; (PROGN)
;; VECTOR)
;; (generate-deinterleave 'deinterleave-16 16)
;; -->
;; (DEFUN DEINTERLEAVE-16 (VECTOR)
;; (ASSERT (= 16 (LENGTH VECTOR)))
;; (PROGN)
;; (LET ((T1 (ELT VECTOR 7)) T2)
;; (SETF T2 (ELT VECTOR 11) (ELT VECTOR 11) T1)
;; (SETF T1 (ELT VECTOR 13) (ELT VECTOR 13) T2)
;; (SETF T2 (ELT VECTOR 14) (ELT VECTOR 14) T1)
;; (SETF (ELT VECTOR 7) T2))
;; (ROTATEF (ELT VECTOR 5) (ELT VECTOR 10))
;; (LET ((T1 (ELT VECTOR 3)) T2)
;; (SETF T2 (ELT VECTOR 9) (ELT VECTOR 9) T1)
;; (SETF T1 (ELT VECTOR 12) (ELT VECTOR 12) T2)
;; (SETF T2 (ELT VECTOR 6) (ELT VECTOR 6) T1)
;; (SETF (ELT VECTOR 3) T2))
;; (LET ((T1 (ELT VECTOR 1)) T2)
;; (SETF T2 (ELT VECTOR 8) (ELT VECTOR 8) T1)
;; (SETF T1 (ELT VECTOR 4) (ELT VECTOR 4) T2)
;; (SETF T2 (ELT VECTOR 2) (ELT VECTOR 2) T1)
;; (SETF (ELT VECTOR 1) T2))
;; (PROGN)
;; VECTOR)
;; (define-interleave-functions interleave-16 deinterleave-16 16)
;; -->
;; INTERLEAVE-16
;; DEINTERLEAVE-16
;;
;; (interleave-16 (iota 16))
;; -->
;; (0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 15)
;;
;; (deinterleave-16 (interleave-16 (iota 16)))
;; -->
;; (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
--
__Pascal Bourguignon__
bartc
"Pascal J. Bourguignon" <p...@informatimago.com> wrote in message
news:7ceiqyu...@pbourguignon.anevia.com...
> ;;; Most of the following code is meta programming. That is, the
> ;;; complexities of the algorithms don't matter at run-time, only when
> ;;; the wanted interleave and deinterleave algorithms are generated.
Sounds like a cheat. You mean you're allowed to use any number of complex
data structures and take any amount of time, because the output is another
program which does the task by a linear series of simple steps (eg.
assignments or swaps)?
--
Bartc
bartc
>> On Aug 25, 8:00 pm, p...@informatimago.com (Pascal J. Bourguignon)
>> wrote:
>>> mike3 <mike4...@yahoo.com> writes:
>>>> Is there a fast algorithm to compute the "interleave" and
>>>> "deinterleave" permutation of any even-number-length data in-place?
>>>
>>> Yes. Any in place permutation can be implemented in O(1) space and
>>> O(n) time, n being the length of the sequence.
>>>
>>
>> So what would be a good in-place algorithm for this permutation?
> But, is it allowed to have an array of marker bits corresponding to each
> element?
This is a neater version. As for speed, this interpreted code interleaved
one million short strings in a fraction of a second. The 'mark' array
overhead can be one bit per element.
a:=("one","two","three","four","five","six","seven","eight","nine","ten")
mark:=(0,)*a.upb
m:=a.upb % 2
println "Original = ",a
for i:=1 to a.upb do
if not mark[i] then
j:=i
x:=a[j]
startj:=j
do
k:=(j<=m | j*2-1 | (j-m)*2)
if k=startj then
a[startj]:=x
mark[startj]:=1
exit
fi
x swap a[k]
mark[k]:=1
j:=k
end
fi
end
println "Interleaved = ",a
Output:
Original = (one,two,three,four,five,six,seven,eight,nine,ten)
Interleaved = (one,six,two,seven,three,eight,four,nine,five,ten)
--
bartc
Pascal J. Bourguignon
Yes, I might have misinterpreted the requirements.
For any even length, I provide a couple of interleave/deinterleave.
Perhaps we want a couple of interleave/deinterleave working for any
even length.
However, this is not a big problem. Instead of generating
instructions to rotate the slots, we can as well execute them
directly. Indeed, if the functions must take vectors of any even
length, the time complexity stays the same since all the generating
functions are O(n), and only the space complexity goes to O(n) from
O(1) to find the cycles.
(defun execute-cycle-swaps (cycle vector)
"
CYCLE: A list of positions.
The meaning of (a0... ai aj ... an) is that
the aith element goes to the ajth position, and
the anth element goes to the a0th position.
DO: Rotate the elements of vector according to the cycle.
"
(case (length cycle)
((0 1)) ; nothing to do.
((2) (rotatef (elt vector (first cycle))
(elt vector (second cycle))))
(otherwise
(let ((t1 (elt vector (first cycle)))
t2)
(loop
:for step :from 0
:for j :in (rest cycle)
:do (if (evenp step)
(setf t2 (elt vector j)
(elt vector j) t1)
(setf t1 (elt vector j)
(elt vector j) t2))
:finally (if (evenp step)
(setf (elt vector (first cycle)) t1)
(setf (elt vector (first cycle)) t2))))))
vector)
(defun interleave (vector)
(let ((length (length vector)))
(assert (evenp length))
(dolist (cycle (permutation-cycles ; O(n) time, O(n) space
(interleave-permutation length))) ; O(n) time, O(1) space
(execute-cycle-swaps cycle vector)) ; O(n) time, O(1) space
vector))
;;; The loop doesn't introduce a multiplicative factor in the time
;;; complexity since permutation-cycles returns a partition of the
;;; input vector.
;;; and similarly for deinterleave:
(defun deinterleave (vector)
(let ((length (length vector)))
(assert (evenp length))
(dolist (cycle (permutation-cycles (interleave-permutation length)))
(execute-cycle-swaps (reverse cycle) vector))
vector))
;; (loop :for i :from 0 :to 20 :by 2 :do (print (interleave (iota i))))
;; -->
;; (0)
;; (0 1)
;; (0 2 1 3)
;; (0 3 1 4 2 5)
;; (0 4 1 5 2 6 3 7)
;; (0 5 1 6 2 7 3 8 4 9)
;; (0 6 1 7 2 8 3 9 4 10 5 11)
;; (0 7 1 8 2 9 3 10 4 11 5 12 6 13)
;; (0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 15)
;; (0 9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8 17)
;; (0 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19)
;; NIL
;;
;; (loop :for i :from 0 :to 20 :by 2 :do (print (deinterleave (interleave (iota i)))))
;; -->
;; ()
;; (0 1)
;; (0 1 2 3)
;; (0 1 2 3 4 5)
;; (0 1 2 3 4 5 6 7)
;; (0 1 2 3 4 5 6 7 8 9)
;; (0 1 2 3 4 5 6 7 8 9 10 11)
;; (0 1 2 3 4 5 6 7 8 9 10 11 12 13)
;; (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
;; (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17)
;; (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19)
;; NIL
However, permutation-cycle is more general than needed since it works
on any kind of permutations not only on interleave and deinterleave
permutations), so it might be possible to reduce the temporary storage
requirements to O(1).
The difficult part is in finding the cycles. Perhaps it is possible
to build them directly from the length of the vector, but I'd guess
it'd involve complicated prime arithmetic...
(loop :for i :from 0 :to 30 :by 2 :do (print (permutation-cycles (interleave-permutation i))))
-->
()
((1) (0))
((3) (2 1) (0))
((5) (2 4 3 1) (0))
((7) (6 5 3) (2 4 1) (0))
((9) (6 3) (2 4 8 7 5 1) (0))
((11) (2 4 8 5 10 9 7 3 6 1) (0))
((13) (2 4 8 3 6 12 11 9 5 10 7 1) (0))
((15) (14 13 11 7) (10 5) (6 12 9 3) (2 4 8 1) (0))
((17) (6 12 7 14 11 5 10 3) (2 4 8 16 15 13 9 1) (0))
((19) (2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1) (0))
((21) (18 15 9) (14 7) (10 20 19 17 13 5) (6 12 3) (2 4 8 16 11 1) (0))
((23) (10 20 17 11 22 21 19 15 7 14 5) (2 4 8 16 9 18 13 3 6 12 1) (0))
((25) (10 20 15 5) (2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1) (0))
((27) (18 9) (6 12 24 21 15 3) (2 4 8 16 5 10 20 13 26 25 23 19 11 22 17 7 14 1) (0))
((29) (2 4 8 16 3 6 12 24 19 9 18 7 14 28 27 25 21 13 26 23 17 5 10 20 11 22 15 1) (0))
--
__Pascal Bourguignon__
Moi
> mike3 said:
> I won't pretend to have an algorithm for you, but I do have a suggestion
> as to how you might break the problem down a bit.
>
> Firstly, identify how many "rings" there are in the data set. In your
> example, there are four: 0 -> 0 (nice and short), 9 -> 9 (that one's
> fine), 3 -> 6 -> 3, and 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1.
>
> That's the tricky bit (programmatically speaking, although it's easy by
> eye). The next bit is trivial: deal with one ring at a time, using the
> standard swap, temp = x, x = y, y = temp (extending as necessary for the
> length of the ring). Rings with only one element can of course be
> ignored.
>
> De-interleaving can be done similarly.
>
> So the hard bit is identifying the rings without using O(n) space. Any
> ideas, folks?
It appears there are always 3 "rings".
Omitting the 0->0 and 9->9 no-op rings, the whole permutation
can be performed by walking 1 "ring".
Starting at 1 and ending at 1 seems the obvious choice.
AvK
Richard Heathfield
> On Wed, 26 Aug 2009 10:39:53 +0000, Richard Heathfield wrote:
>
>> mike3 said:
>
>> I won't pretend to have an algorithm for you, but I do have a
>> suggestion as to how you might break the problem down a bit.
>>
>> Firstly, identify how many "rings" there are in the data set. In
>> your example, there are four: 0 -> 0 (nice and short), 9 -> 9 (that
>> one's fine), 3 -> 6 -> 3, and 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1.
>>
>> That's the tricky bit (programmatically speaking, although it's
>> easy by eye). The next bit is trivial: deal with one ring at a
>> time, using the standard swap, temp = x, x = y, y = temp (extending
>> as necessary for the length of the ring). Rings with only one
>> element can of course be ignored.
>>
>> De-interleaving can be done similarly.
>>
>> So the hard bit is identifying the rings without using O(n) space.
>> Any ideas, folks?
>
> It appears there are always 3 "rings".
And yet, in the example posted by the OP, there are four.
> Omitting the 0->0 and 9->9 no-op rings, the whole permutation
> can be performed by walking 1 "ring".
> Starting at 1 and ending at 1 seems the obvious choice.
And then you end up with 3 and 6 in the wrong place.
Pascal J. Bourguignon
> It appears there are always 3 "rings".
You have not been reading my articles...
--
__Pascal Bourguignon__
Willem
) functions are O(n), and only the space complexity goes to O(n) from
) O(1) to find the cycles.
Which goes directly against the requirements.
If we can use O(n) space, then using a temporary target array
is far easier than any cycling/permutation algorithm.
Moi
> Moi said:
>
> And yet, in the example posted by the OP, there are four.
>
>> Omitting the 0->0 and 9->9 no-op rings, the whole permutation can be
>> performed by walking 1 "ring". Starting at 1 and ending at 1 seems the
>> obvious choice.
>
> And then you end up with 3 and 6 in the wrong place.
Oops. Back to the old drawing board...
AvK
bartc
"Willem" <wil...@stack.nl> wrote in message
news:slrnh9aim8....@turtle.stack.nl...
> Pascal J. Bourguignon wrote:
> ) functions are O(n), and only the space complexity goes to O(n) from
> ) O(1) to find the cycles.
>
> Which goes directly against the requirements.
>
> If we can use O(n) space, then using a temporary target array
> is far easier than any cycling/permutation algorithm.
A temporary array will take as much space as the original. An O(n) workspace
could potentially require much less, depend on how complex the elements to
be processed are. (The solution I posted requires 1 bit per element; I don't
know about the lisp code. He anyway mentions the possibility of O(1) later
on)
--
bartc
ekkehard.horner
> Hi.
>
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length data in-place?
>
> 0123456789
> becomes
> 0516273849
> (interleave)
>
>
> 0516273849
> becomes
> 0123456789
> (deinterleave)
>
> That is, the "interleave" permutation takes the two halves of the
> sequence and interleaves them together, while the "deinterleave" does
> the opposite.
As I developed the algorithm in VBScript and 'ported' it to C, the
implementation needs further work and I can't say anything about
efficiency, but I hope the principle is easy to see.
#include <stdio.h>
void interleaveArrInPlace( char * aSrc, unsigned nUB, int nStep );
void deinterleaveArrInPlace( char * aSrc, unsigned nUB, int nStep );
int main(int argc, char ** argv) {
char * aSrc = "0123456789";
char * aExp = "0516273849";
fprintf( stderr, "%s begin\n", *argv );
fprintf( stdout, "Src: %s\n", aSrc );
interleaveArrInPlace( aSrc, strlen( aSrc ) - 1, 0 );
fprintf( stdout, "I: %s\n", aSrc );
fprintf( stdout, "Exp: %s\n", aExp );
deinterleaveArrInPlace( aSrc, strlen( aSrc ) - 1, 0 );
fprintf( stdout, "D: %s\n", aSrc );
fprintf( stderr, "%s end\n", *argv );
return 0;
}
/** interleave/zip halves of aSrc in place
----------------------------------------------------------------------------
how it works: swap from the inside out:
0 : 0 1 2 3 4 5 6 7 8 9 4 4
X
1 : 0 1 2 3 5 4 6 7 8 9 3 5
X X
2 : 0 1 2 5 3 6 4 7 8 9 2 6
X X X
3 : 0 1 5 2 6 3 7 4 8 9 1 7
X X X X
I Inp: 0 5 1 6 2 7 3 8 4 9 True
----------------------------------------------------------------------------
*/
void interleaveArrInPlace( char * aSrc, unsigned nUB, int nStep ) {
int nUBH = nUB / 2;
int nFrom = nUBH - nStep;
int nTo = nUBH + nStep;
int nPos;
char vTmp;
if (-1 == nUB) { return; }
if ( 0 == (nUB % 2)) { return; }
if ( 1 > nFrom) { return; }
for (nPos = nFrom; nPos <= nTo; nPos += 2) {
vTmp = aSrc[ nPos ];
aSrc[ nPos ] = aSrc[ nPos + 1 ];
aSrc[ nPos + 1 ] = vTmp;
}
if (1 < nFrom) { interleaveArrInPlace( aSrc, nUB, nStep + 1 ); }
}
/** deinterleave/unzip 'halves' of aSrc in place
----------------------------------------------------------------------------
how it works: swap from the outside in:
0 : 8 1 6 3 4 5 2 7 0 9 1 8
X X X X
1 : 8 6 1 4 3 2 5 0 7 9 2 7
X X X
2 : 8 6 4 1 2 3 0 5 7 9 3 6
X X
3 : 8 6 4 2 1 0 3 5 7 9 4 5
X
D Inp: 8 6 4 2 0 1 3 5 7 9 True
----------------------------------------------------------------------------
*/
void deinterleaveArrInPlace( char * aSrc, unsigned nUB, int nStep ) {
int nFrom = nStep + 1;
int nTo = nUB - nFrom;
int nPos;
int vTmp;
if (-1 == nUB) { return; }
if (0 == (nUB % 2)) { return; }
if (nFrom >= nTo) { return; }
for (nPos = nFrom; nPos <= nTo; nPos += 2) {
vTmp = aSrc[ nPos ];
aSrc[ nPos ] = aSrc[ nPos + 1 ];
aSrc[ nPos + 1 ] = vTmp;
}
if (1 < (nTo - nFrom)) { deinterleaveArrInPlace( aSrc, nUB, nFrom ); }
}
output:
tinterleave_vc.exe begin
Src: 0123456789
I: 0516273849
Exp: 0516273849
D: 0123456789
tinterleave_vc.exe end
Pascal J. Bourguignon
> This is a neater version. As for speed, this interpreted code
> interleaved one million short strings in a fraction of a second. The
> mark' array overhead can be one bit per element.
Of course, absolute speed is not much a matter with the current
computer and small problem sizes. But if you had a vector of 7
billion items (ie. as soon as you want to process data about each
human, that is as soon as the NSA or Google...), matters would be
different, O(n) would import.
So you have O(n) time and O(n) space.
--
__Pascal Bourguignon__
Pascal J. Bourguignon
> mike3 schrieb:
>> Hi.
>> Is there a fast algorithm to compute the "interleave" and
>> "deinterleave" permutation of any even-number-length data in-place?
>> Like this:
>> 0123456789
>> becomes
>> 0516273849
>> (interleave)
>> and
>> 0516273849
>> becomes
>> 0123456789
>> (deinterleave)
>> That is, the "interleave" permutation takes the two halves of the
>> sequence and interleaves them together, while the "deinterleave" does
>> the opposite.
>
> As I developed the algorithm in VBScript and 'ported' it to C, the
> implementation needs further work and I can't say anything about
> efficiency, but I hope the principle is easy to see.
> [...]
Sorry, but it doesn't work with inputs of any even lengths.
If I add items to aSrc and aExp:
> int main(int argc, char ** argv) {
> char * aSrc = "0123456789ABCD";
> char * aExp = "0718293A4B5C6D";
it breaks:
$ ./ekkehard
./ekkehard begin
Src: 0123456789ABCD
Bus error
On the other hand:
C/USER[118]> (setf *print-base* 16.)
10
C/USER[119]> (interleave (iota 14))
(0 7 1 8 2 9 3 A 4 B 5 C 6 D)
C/USER[120]> (deinterleave (interleave (iota 14)))
(0 1 2 3 4 5 6 7 8 9 A B C D)
--
__Pascal Bourguignon__
bartc
> "bartc" <ba...@freeuk.com> writes:
>> mark:=(0,)*a.upb
>> m:=a.upb % 2
>> for i:=1 to a.upb do
>> if not mark[i] then
>> j:=i
>> x:=a[j]
>> startj:=j
>> repeat # I've simplified this inner loop...
>> k:=(j<=m | j*2-1 | (j-m)*2)
>> x swap a[k]
>> mark[k]:=1
>> j:=k
>> until j=startj
>> fi
>> end
>
> So you have O(n) time and O(n) space.
I expected it to be nearer O(n**2) time because of the two loops..
On the O(n) workspace:
The OP didn't give too much away. Perhaps the data to be interleaved has
large entities, and 1-bit-per-element overhead is acceptable. In any case I
haven't yet seen an algorithm or code posted that used O(1) workspace
(unless that was buried in your Lisp code somewhere).
This little problem was more difficult than it looked. And the behaviour
above is weird. With N=100000, there are some 200 internal 'cycles'
executed. With N=200000, there are 2.
--
Bartc
bartc
It worked for me with one C compiler, failed on another. So it seems to work
in principle. Maybe it should have been left in VBScript.
--
Bartc
John W. Krahn
>
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length data in-place?
> Like this:
>
> 0123456789
> becomes
> 0516273849
> (interleave)
>
> and
>
> 0516273849
> becomes
> 0123456789
> (deinterleave)
>
> That is, the "interleave" permutation takes the two halves of the
> sequence and interleaves them together, while the "deinterleave" does
> the opposite.
$ perl -le'
my $x = "0123456789";
print $x;
for my $i ( reverse 1 .. length( $x ) / 2 ) {
substr $x, $i, 0, substr $x, -1, 1, "";
}
print $x;
'
0123456789
0516273849
$ perl -le'
my $x = "0516273849";
print $x;
for my $i ( 1 .. length( $x ) / 2 ) {
substr $x, $i, 0, substr $x, $i * 2, 1, "";
}
print $x;
'
0516273849
0123456789
John
--
Those people who think they know everything are a great
annoyance to those of us who do. -- Isaac Asimov
Pascal J. Bourguignon
> So the hard bit is identifying the rings without using O(n) space. Any
> ideas, folks?
The question is whether it'd be possible to "construct" the cycles
from the length of the input vector (with formulas, like we can
compute the permutation images).
I don't know if it's possible. (I'd bet on no).
Have a look at some graphs I've made:
http://www.informatimago.com/misc/interleave/
The number of cycles and their sizes don't seem to depend in any
obvious way on the length of the input vectors.
--
__Pascal Bourguignon__
Pascal J. Bourguignon
> "Pascal J. Bourguignon" <p...@informatimago.com> wrote in message
> news:87skfet...@galatea.local...
>> "bartc" <ba...@freeuk.com> writes:
>
>>> mark:=(0,)*a.upb
>>> m:=a.upb % 2
>
>>> for i:=1 to a.upb do
>>> if not mark[i] then
>>> j:=i
>>> x:=a[j]
>>> startj:=j
>>> repeat # I've simplified this inner loop...
>>> k:=(j<=m | j*2-1 | (j-m)*2)
>>> x swap a[k]
>>> mark[k]:=1
>>> j:=k
>>> until j=startj
>>> fi
>>> end
>
>>
>> So you have O(n) time and O(n) space.
>
> I expected it to be nearer O(n**2) time because of the two loops..
Thanks to the marks, we really visit each node only once.
> On the O(n) workspace:
>
> The OP didn't give too much away. Perhaps the data to be interleaved
> has large entities, and 1-bit-per-element overhead is acceptable. In
> any case I haven't yet seen an algorithm or code posted that used O(1)
> workspace (unless that was buried in your Lisp code somewhere).
Indeed, I use also a vector of booleans to mark the visited nodes.
> This little problem was more difficult than it looked. And the
> behaviour above is weird. With N=100000, there are some 200 internal
> cycles' executed. With N=200000, there are 2.
Yes, it's weird.
I think it's probably related to finite groups and their
classification, but I don't know enough about them, and much less if
some theorem would exist that would allow us to build the cycles in
O(n) time and O(1) space.
On http://www.informatimago.com/misc/interleave/ I show the
factorization of n and n-1 along with the number of cycles and their
lengths, but I can see no correlation.
Of course, if we constraint O(1) space, we can always identify the
cycles by walking each of them as many times as there are nodes in
them (ie. in O(n�))
--
__Pascal Bourguignon__
Pascal J. Bourguignon
Well, I didn't check the C code more closely, because I think there's
a principle problem with the approach: when you are not in the special
p
cases where n = Σ i = (p+1)*p/2
i=1
which is true for n = 10 with p = 4 [ (4+1)*4/2 = 10 ], n = 15, n =
21, etc, then you don't get the nice triangle of swaps, so your
algorithm doesn't work in general.
--
__Pascal Bourguignon__
mike3
Geez... it appears this seemingly simple problem
is a lot harder than I thought it would be...
Richard Heathfield
> Richard Heathfield <r...@see.sig.invalid> writes:
>> So the hard bit is identifying the rings without using O(n) space.
>> Any ideas, folks?
>
> The question is whether it'd be possible to "construct" the cycles
> from the length of the input vector (with formulas, like we can
> compute the permutation images).
Alternatively, you can just work them out as you go along, which
someone has already explained how to do.
> I don't know if it's possible. (I'd bet on no).
> Have a look at some graphs I've made:
> http://www.informatimago.com/misc/interleave/
Very pretty (no, I mean it - the arrow pattern is very striking), but
a bit of a dead end in computational terms.
> The number of cycles and their sizes don't seem to depend in any
> obvious way on the length of the input vectors.
Research project! Research project!
rossum
<r...@see.sig.invalid> wrote:
>Pascal J. Bourguignon said:
>
>> Richard Heathfield <r...@see.sig.invalid> writes:
>>> So the hard bit is identifying the rings without using O(n) space.
>>> Any ideas, folks?
>>
>> The question is whether it'd be possible to "construct" the cycles
>> from the length of the input vector (with formulas, like we can
>> compute the permutation images).
>
>Alternatively, you can just work them out as you go along, which
>someone has already explained how to do.
You can do it in in the case from the OP, where the information about
the original position in the array is already present in the data;
that allows you to tell if a particular entry is correctly or
incorrectly positioned. In the general case, where the original
position is not implicit in the data then you will need O(n) extra
memory to add an "initial position" tag to the data. That would make
an "in-place" method impossible.
rossum
Steven G. Johnson
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length datain-place?
> Like this:
This is exactly an in-place transposition of a 2xN matrix into an Nx2
matrix, stored in row-major order (contiguous rows).
This problem is highly nontrivial, but has been studied by numerous
authors since the 1950s, and several in-place non-square transpose
algorithms are known. See:
http://en.wikipedia.org/wiki/In-place_matrix_transposition
for an overview of the literature and mathematics of this problem and
links to free source code.
Regards,
Steven G. Johnson
PS. I should also say that an out-of-place implementation is likely to
be much faster than any in-place algorithm for this problem, unless
your individual data items are much larger than single numbers. In-
place non-square transposition algorithms tend to have poor spatial
locality and hence don't efficiently use the cache.
Willem
) Well, I didn't check the C code more closely, because I think there's
) a principle problem with the approach: when you are not in the special
)
) p
) cases where n = ? i = (p+1)*p/2
) i=1
)
) which is true for n = 10 with p = 4 [ (4+1)*4/2 = 10 ], n = 15, n =
) 21, etc, then you don't get the nice triangle of swaps, so your
) algorithm doesn't work in general.
Why ? I tried it with 14 numbers (by hand) and it works.
It quite simply 'bubbles' the two sequences together.
That there happens to be a triangle doesn't mean it only works
for triangle numbers.
However, the main problem is that it's not O(n) time.
Richard Harter
<mike...@yahoo.com> wrote:
>Hi.
>
>Is there a fast algorithm to compute the "interleave" and
>"deinterleave" permutation of any even-number-length data in-place?
>Like this:
>
>0123456789
>becomes
>0516273849
>(interleave)
>
>and
>
>0516273849
>becomes
>0123456789
>(deinterleave)
>
>That is, the "interleave" permutation takes the two halves of the
>sequence and interleaves them together, while the "deinterleave" does
>the opposite.
As a note, this is equivalent to transposing a nX2 matrix (or 2Xn
depending on your conventions). One way to do this is to
recursively swap center sections. Thus if s = <abcd> where s and
a,b,c,d are array segments we swap b and c and then process <ac>
and <bd>. (There is the question of how to handle odd length
segments but this is not beyond the abilities of my readers.)
This algorithm is O(n log n) - however if n is large it may be
faster than cycle chasing because it has good locality.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
No one asks if a tree falls in the forest
if there is no one there to see it fall.
mike3
Yeah, the elements are quite a bit bigger than single numbers.
The problem with out of place though is the additional storage
required.
ekkehard.horner
> Pascal J. Bourguignon wrote:
> ) Well, I didn't check the C code more closely, because I think there's
> ) a principle problem with the approach: when you are not in the special
> )
> ) p
> ) cases where n = ? i = (p+1)*p/2
> ) i=1
> )
> ) which is true for n = 10 with p = 4 [ (4+1)*4/2 = 10 ], n = 15, n =
> ) 21, etc, then you don't get the nice triangle of swaps, so your
> ) algorithm doesn't work in general.
>
> Why ? I tried it with 14 numbers (by hand) and it works.
> It quite simply 'bubbles' the two sequences together.
> That there happens to be a triangle doesn't mean it only works
> for triangle numbers.
Thanks for that; without this encouragement, I'd probably still hesitate
to
(1) admit to my blunder - if you replace the evil
int main(int argc, char ** argv) {
char * aSrc = "0123456789";
char * aExp = "0516273849";
with
int main(int argc, char ** argv) {
char aSrc[] = "0123456789";
char * aExp = "0516273849";
vc *and* gcc will be happy.
(2) stand by my claim that this approach 'works correctly' - at least
for even numbered strings (but see (4)); I excluded odd numbered
strings because of (3)
(3) ask if there are principles/arguments for the decision, what the result
of interleaving an odd numbered string should be (e.g. do you agree with
the outcome of the sample in (5)?)
> However, the main problem is that it's not O(n) time.
(4) say that in addition to the speed problem, the recursive implementation
was a bad idea; it's no use to save data memory if you overflow the stack
(5) show my attempt at implementing John W. Krahn's algorithm in C:
/*
----------------------------------------------------------------------------
sub interleaveKrahn00 {
for my $i ( reverse 1 .. length( $_[ 0 ] ) / 2 ) {
substr $_[ 0 ], $i, 0, substr $_[ 0 ], -1, 1, "";
}
}
----------------------------------------------------------------------------
0123456789A 0123456789
v----^ v---^
01234A56789 0123495678
v-----^ v----^
012394A5678 0123849567
v------^ v-----^
0128394A567 0127384956
v-------^ v------^
01728394A56 0162738495
v--------^ v-------^
061728394A5 0516273849
----------------------------------------------------------------------------
*/
void interleaveKrahn01( char * aSrc ) {
unsigned uiLen = strlen( aSrc );
unsigned uiHalf = uiLen / 2;
unsigned uiLast = uiLen - 1;
char * pLast = aSrc + uiLast;
char * pIns = aSrc + uiHalf;
for ( ; pIns > aSrc; --pIns ) {
char tmp = *pLast;
memmove( pIns + 1, pIns, pLast - pIns );
*pIns = tmp;
}
}
(all errors mine)
[...]
Tim Rentsch
> Hi.
>
> Is there a fast algorithm to compute the "interleave" and
> "deinterleave" permutation of any even-number-length data in-place?
> Like this:
>
> 0123456789
> becomes
> 0516273849
> (interleave)
>
> and
>
> 0516273849
> becomes
> 0123456789
> (deinterleave)
>
> That is, the "interleave" permutation takes the two halves of the
> sequence and interleaves them together, while the "deinterleave" does
> the opposite.
The following routine takes an array of int's,
but it's easy to see how to modify it to take
elements of an arbitrary type.
typedef unsigned long Index;
extern void
interleave_array( Index n, int a[ n+n ] ){
Index i, s, t;
int e;
for( i = 1; i < n; i += 2 ){
if( i == next_s( i, n ) ) continue;
s = i;
do s = next_s( s, n ); while( s > i );
if( s < i ) continue;
for(
e = a[s];
t = next_s( s, n ), a[s] = a[t], t != i;
s = t
) {}
a[s] = e;
}
}
#define is_odd(x) ((x)&1ul)
#define is_even(x) (! is_odd(x) )
static Index
next_s( Index s, Index n ){
if( is_odd( s ) ) return n + (s-1)/2;
if( is_even( s ) ) return s/2;
}
Takes O(1) space.
Worst-case run time seems to be O( n log(n) ).
I can't prove that, but I bet Don Knuth could.
The analogous de-interleave routine is left as
an exercise for the reader.
Tim Rentsch
I think the original request is for O(1) total space taken,
rather than O( log n ) total space as this sort of recursive
version would take.
Richard Harter
<t...@alumnus.caltech.edu> wrote:
Yes and no. If you code it using recursion, yes. However you
don't need recursive function calls - because it is an array the
address identifies where the code is in the tree of actions.
Ergo, you can do it in O(1) space.
rossum
wrote:
>Hi.
>
>Is there a fast algorithm to compute the "interleave" and
>"deinterleave" permutation of any even-number-length data in-place?
There is an in-place algorithm, but I am not sure how fast it is. If
your data items are very large then you may be better off using a
different algorithm to interleave an array of pointers to the data
while leaving the data itself unmoved.
The in-place algorithm works by rotating a chunk of the array:
abcdef -> aDBCef
The rotation has placed two items (d and b) in their correct
positions. Move the start of the chunk to be rotated forward by two
and the end point forward by one. Repeat until the array is all
processed. At each low position the algorithm looks for "what item
needs to be moved into this position" and rotates it into position.
Because you are interleaving that also gives you the next data item in
position 'for free'. The high end of the rotation steps through the
upper half of the array, moving each item back to its correct
position. The low end drops off one item every rotation. These two
processes combine to give the interleaving.
The Java code looks like:
// Interleaves the given array in-place.
void interleave(int[] ary) {
// hi = start of upper half of interleave.
int hi = (ary.length + (ary.length % 2)) / 2;
for (int lo = 1; lo < hi; lo += 2) {
rotate(ary, lo, hi);
++hi;
}
} // end interleave()
// Rotates the part of the array between
// the lo and hi indices inclusive.
void rotate(int[] ary, int lo, int hi) {
int temp = ary[hi];
for (int i = hi; i > lo; --i) {
ary[i] = ary[i-1];
}
ary[lo] = temp;
} // end rotate()
This code is written for clarity, not for speed.
I have tested it on all arrays from {0} to {0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11} inclusive, and it worked fine.
rossum
rossum
I suspect that it might be O(log n) space as you need to index into
the array to do any work, and the size of the indexes required will be
as log n. If the array has more than 2^64 entries then you cannot use
a 64 bit long to index it.
rossum
Richard Harter
We're not counting the index size. :-)
Well, no, it's not a joke. If we don't implicitly assume that
indices, pointers, and objects are O(1) in space pretty much all
algorithms are at least O(log n) in space.
It is well to remember in these discussions that O() space and
O() time do not refer to the actual performance of computers
(which are bounded in space and time and do not have asymptotic
behaviour) but rather to models of computer performance.
What is usually going on but is almost never spelled out
explicitly is that algorithm analysis customarily assumes the
behaviour of an abstract machine with unbounded resources that
behaves "in the same" way as a real computer. This implies that
things and operations that are fixed in size and performance in
real computers should be treated as as O(1) costs.
pete
> On Aug 25, 7:31 pm, Sjouke Burry <burrynulnulf...@ppllaanneett.nnll>
> wrote:
>
>>mike3 wrote:
>>
>>>Hi.
>>
>>>Is there a fast algorithm to compute the "interleave" and
>>>"deinterleave" permutation of any even-number-length data in-place?
>>>Like this:
>>
>>>0123456789
>>>becomes
>>>0516273849
>>>(interleave)
>>
>>>and
>>
>>>0516273849
>>>becomes
>>>0123456789
>>>(deinterleave)
>>
>>>That is, the "interleave" permutation takes the two halves of the
>>>sequence and interleaves them together, while the "deinterleave" does
>>>the opposite.
>>
>> loop:adr=(adr+6)%10;
>> out(adr)=in(i);
>> i++;
>> until i==10;
>
>
> Is this an in-place method? As I wanted an in-place algorithm.
This is in place, but the running time is O(N*N):
/* BEGIN interleave.c output */
zero one two three four five six seven 8 9 10 11 12 13 14 15
zero 8 one 9 two 10 three 11 four 12 five 13 six 14 seven 15
/* END interleave.c output */
/* BEGIN interleave.c */
#include <stdio.h>
#define STRINGS \
"zero","one","two","three","four",\
"five","six","seven","8","9","10",\
"11","12","13","14","15"
#define NMEMB(A) (sizeof(A) / sizeof*(A))
void interleave(void *base, size_t nmemb, size_t size);
void insert(void *base, size_t nmemb, size_t size);
int main(void)
{
char *string[] = {
STRINGS
};
size_t index;
puts("/* BEGIN interleave.c output */\n");
for (index = 0; index != NMEMB(string); ++index) {
printf("%s ", string[index]);
}
puts("\n");
interleave(string, NMEMB(string), sizeof *string);
for (index = 0; index != NMEMB(string); ++index) {
printf("%s ", string[index]);
}
puts("\n");
puts("/* END interleave.c output */");
return 0;
}
void interleave(void *base, size_t nmemb, size_t size)
{
char *array = base;
size_t index = size;
nmemb = nmemb / 2 + nmemb % 2;
while (nmemb-- > 1) {
insert(array + index, nmemb, size);
index += size + size;
}
}
void insert(void *base, size_t nmemb, size_t size)
{
unsigned char *end = base;
unsigned char *p = end + nmemb * size;
unsigned char *const after = p + size;
do {
unsigned char *p1 = p;
unsigned char *p2 = p1;
const unsigned char temp = *p1;
do {
*p1 = *(p2 -= size);
} while ((p1 = p2) != end);
*p1 = temp;
++end;
} while (++p != after);
}
/* END interleave.c */
--
pete