Рекурсивная перестановочная перестановка

Question

У меня есть программа (фрактал), которая рисует линии в чересстрочном порядке. Первоначально, учитывая H Линии рисовать, это определяет количество кадров Nи рисует каждый Nй кадр, то каждый N+1кадр и т. д.

Например, если H = 10 а также N = 3Рисует их по порядку:

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

Однако мне не нравилось, как полосы будут постепенно сгущаться, оставляя большие области между неиспользованными в течение длительного времени. Таким образом, метод был усовершенствован для рекурсивного рисования линий средней точки в каждой группе вместо непосредственно последующих, например:

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

(Числа в скобках выходят за пределы диапазона и не отображаются.) Алгоритм довольно прост:

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.

Когда нечетные кадры отрисовываются на последнем размере шага, они отрисовываются в простом порядке, так же как и начальный (раздражающий) метод. То же самое с каждым четвертым кадром и т. Д. Это не так плохо, потому что некоторые промежуточные кадры уже нарисованы.

Но та же перестановка может быть рекурсивно применена к элементам для каждого размера шага. В приведенном выше примере последняя строка изменится на:

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

В предыдущих строках слишком мало элементов, чтобы рекурсия вступила в силу. Но если N было достаточно большим, для некоторых строк может потребоваться несколько уровней рекурсии. Любой размер шага с 3 или более соответствующими элементами может быть рекурсивно переставлен.

Вопрос 1. Есть ли общее название для этой перестановки на N элементы, которые я мог бы использовать, чтобы найти дополнительный материал на нем? Я также интересуюсь любыми подобными примерами, которые могут существовать. Я был бы удивлен, если бы я был первым человеком, который хочет сделать это.

Вопрос 2. Могу ли я использовать некоторые методы для его вычисления? Я работаю в C, но меня больше интересует уровень алгоритма на данном этапе; Я с удовольствием читаю код на другом языке (в пределах разумного).

Я еще не взялся за его реализацию. Я ожидаю, что я предварительно вычислю перестановку (в отличие от алгоритма для предыдущего метода, выше). Но мне также интересно, есть ли простой способ получить следующий кадр для рисования без предварительного вычисления, похожий по сложности на предыдущий метод.

Answer 1

Звучит так, как будто вы пытаетесь построить одномерные последовательности с низким расхождением. Ваша перестановка может быть вычислена путем обращения двоичного представления индекса.

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

Пример использования:

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

Вариант, который работает на общем 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]