递归交错排列

Question

递归交错排列

algorithmlanguage-agnosticrecursionpermutationinterlacing

3

我有一个绘制分形的程序，它以交错顺序绘制线条。最初，给定要绘制的线条数 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语言，但在这个阶段，我更感兴趣的是算法层面；我愿意阅读其他语言的代码（在合理范围内）。

我还没有尝试实现它。我预计首先会预先计算排列（与上述方法的算法相反）。但是，我也很想知道是否有一种简单的方法可以得到下一个要绘制的帧，而不必预先计算它，其复杂度类似于前面的方法。

- Edmund

我感觉自己没有完全理解你的问题，无法回答，但是这个问题与伽罗瓦域（http://en.wikipedia.org/wiki/Finite_field）和拉丁方阵（http://en.wikipedia.org/wiki/Latin_square）有些相似之处。也许在这两者之间寻找答案会更接近你所要求的。 - Gian

哎呀，我怕我打开了高等数学的潘多拉魔盒！我会看看能不能理解那些文章... - Edmund

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Per · Accepted Answer

看起来你正在尝试构建一维低差异序列。你可以通过翻转索引的二进制表示来计算排列。

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]