# Re: "Interleave" permutation algorithm?

On Wed, 26 Aug 2009 12:11:53 +0100, rossum wrote:

On Tue, 25 Aug 2009 22:26:15 -0700 (PDT), mike3 <mike4ty4@xxxxxxxxx>
wrote:

On Aug 25, 9:01 pm, "robertwess...@xxxxxxxxx" <robertwess...@xxxxxxxxx>
wrote:
On Aug 25, 9:07 pm, mike3 <mike4...@xxxxxxxxx> wrote:

On Aug 25, 8:00 pm, p...@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon)
wrote:

mike3 <mike4...@xxxxxxxxx> 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

#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
.