Рекурсивная перестановочная перестановка - PullRequest
Новая
       39

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

3 голосов
/ 18 ноября 2011

У меня есть программа (фрактал), которая рисует линии в чересстрочном порядке.Первоначально, учитывая 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, но меня больше интересует уровень алгоритма на данном этапе;Я рад прочитать код на другом языке (в пределах разумного).

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

1 Ответ

3 голосов
/ 18 ноября 2011

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

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