Recursive interlacing permutation

Question

I have a program (a fractal) that draws lines in an interlaced order. Originally, given H lines to draw, it determines the number of frames N, and draws every Nth frame, then every N+1'th frame, etc.

For example, if H = 10 and N = 3, it draws them in order:

0, 3, 6, 9,
1, 4, 7,
2, 5, 8.

However I didn't like the way bands would gradually thicken, leaving large areas between undrawn for a long time. So the method was enhanced to recursively draw midpoint lines in each group instead of the immediately sebsequent lines, for example:

0, (32)          # S (step size) = 32
8, (24)          # S = 16
4, (12)          # S = 8
2, 6, (10)       # S = 4
1, 3, 5, 7, 9.   # S = 2

(The numbers in parentheses are out of range and not drawn.) The algorithm's pretty simple:

Set S to a power of 2 greater than N*2, set F = 0.
While S > 1:
    Draw frame F.
    Set F = F + S.
    If F >= H, then set S = S / 2; set F = S / 2.

When the odd numbered frames are drawn on the last step size, they are drawn in simple order just as an the initial (annoying) method. The same with every fourth frame, etc. It's not as bad because some intermediate frames have already been drawn.

But the same permutation could recursively be applied to the elements for each step size. In the example above, the last line would change to:

1,      # the 0th element, S' = 16
9,      # 4th, S' = 8
5,      # 2nd, S' = 4
3, 7.   # 1st and 3rd, S' = 2

The previous lines have too few elements for the recursion to take effect. But if N was large enough, some lines might require multiple levels of recursion. Any step size with 3 or more corresponding elements can be recursively permutated.

Question 1. Is there a common name for this permutation on N elements, that I could use to find additional material on it? I am also interested in any similar examples that may exist. I would be surprised if I'm the first person to want to do this.

Question 2. Are there some techniques I could use to compute it? I'm working in C but I'm more interested at the algorithm level at this stage; I'm happy to read code other language (within reason).

I have not yet tackled its implemention. I expect I will precompute the permutation first (contrary to the algorithm for the previous method, above). But I'm also interested if there is a simple way to get the next frame to draw without having to precomputing it, similar in complexity to the previous method.

I don't feel like I've understood what you're asking well enough to answer, but something about this is reminiscent of Galois fields (http://en.wikipedia.org/wiki/Finite_field) and Latin squares (http://en.wikipedia.org/wiki/Latin_square). Perhaps something between those two will lead you to exactly what you're asking. — Gian, Nov 18 '11 at 01:41
Hmm I fear I've opened a Pandora's box of higher maths! I'll see if I can understand any of those articles... — Edmund, Nov 18 '11 at 01:48

Per · Accepted Answer · 2011-11-18T02:35:21.157

3

It sounds as though you're trying to construct one-dimensional low-discrepancy sequences. Your permutation can be computed by reversing the binary representation of the index.

def rev(num_bits, i):
    j = 0
    for k in xrange(num_bits):
        j = (j << 1) | (i & 1)
        i >>= 1
    return j

Example usage:

>>> [rev(4,i) for i in xrange(16)]
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

A variant that works on general n:

def rev(n, i):
    j = 0
    while n >= 2:
        m = i & 1
        if m:
            j += (n + 1) >> 1
        n = (n + 1 - m) >> 1
        i >>= 1
    return j

>>> [rev(10,i) for i in xrange(10)]
[0, 5, 3, 8, 2, 7, 4, 9, 1, 6]

edited Nov 18 '11 at 02:35

answered Nov 18 '11 at 02:01

Per

2,594
12
18

Hmm, I think you're onto something. It is kind of a "quasi random sequence". It is not random but it has several levels of uniform distribution so I guess would pass some of same kinds of tests. – Edmund Nov 18 '11 at 02:08
Yes, I get the same permutation for N = 16 ! But not for N = 10. From your code I end up with `[0, 8, 4, 12, 2, 10, 6, 14, 1, 9]` instead of the desired `[0, 8, 4, 2, 6, 1, 9, 5, 3, 7]`. The numbers that occur in both are in the right order. It looks like I need only calculate the larger permutation and ignore the elements that are out of range. – Edmund Nov 18 '11 at 02:13
@Edmund I posted a version for general `N`. It doesn't give exactly the sequence you specified, but it operates on the same principles. – Per Nov 18 '11 at 02:37
Thanks. (Getting the exactly same sequence is not required for my use case.) – Edmund Nov 18 '11 at 03:08

Recursive interlacing permutation

1 Answers1