arrays - 以特定顺序遍历数组，以便公平地对其进行采样

Question

我想以某种方式遍历数组:
从数组的第一个和最后一个元素开始，我要访问的下一个元素是距离所有先前访问过的元素最远的元素。

对于长度为 n+1 的数组，序列为

• 0,
• n,
• n/2(距离 0 和 n 最远)，
• n/4 和 n*3/4(距离之前所有 3 个指数最远)，
• n/8、n*3/8、n*5/8、n*7/8，(距离之前所有 5 个指数最远)
• n*1/16、n*3/16、n*5/16、n*7/16、n*9/16、n*11/16、n*13/16、n*15/16
• ...

如果 n 不是 2 的幂，那么其中一些数字将不得不向上或向下舍入，但我不确定如何在舍入时避免重复。

最后我想要一个整数序列，它只包含 0 到 n 之间的所有数字一次。 (对于任何 n，不仅仅是二的幂)

这个排列有名字吗？

生成这些数字的函数将如何工作？

我正在寻找可以即时生成这些数字的函数。

如果有十亿个元素，我不想管理所有以前访问过的元素的巨大列表，或者提前生成整个排列列表。

想法是，一旦找到符合特定条件的元素，我就可以中止迭代，因此在大多数情况下我不需要整个排列序列。

所以我正在寻找具有以下属性的函数 f(int currentIndex, int maxIndex):

要对大小为 8 的数组进行交互，我会调用

f(0,8) returns 0, to get the index of the first element
f(1,8) returns 8
f(2,8) returns 4
f(3,8) returns 2
f(4,8) returns 6
f(5,8) returns 1
f(6,8) returns 3
f(7,8) returns 5
f(8,8) returns 7

(我不太确定如何将此示例扩展到不是 2 的幂的数字)

是否有具有这些属性的函数？

Answer 1

您描述的跳跃是 Van der Corput 序列的一个特征，如 a task I wrote on Rosetta Code 中所述.

我有一个精确的函数来重新排序输入序列，但它需要与输入数组一样大的数组。

下面是一个近似解，一个一个生成索引，只取输入数组的长度，然后用常量内存计算索引。

测试给出了例程“好”程度的一些指示。

>>> from fractions import Fraction
>>> from math import ceil
>>> 
>>> def vdc(n, base=2):
    vdc, denom = 0,1
    while n:
        denom *= base
        n, remainder = divmod(n, base)
        vdc += remainder / denom
    return vdc

>>> [vdc(i) for i in range(5)]
[0, 0.5, 0.25, 0.75, 0.125]
>>> def van_der_corput_index(sequence):
    lenseq = len(sequence)
    if lenseq:
        lenseq1 = lenseq - 1
        yield lenseq1   # last element
        for i in range(lenseq1):
            yield ceil(vdc(Fraction(i)) * lenseq1)


>>> seq = list(range(23))
>>> seq
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
>>> list(van_der_corput_index(seq))
[22, 0, 11, 6, 17, 3, 14, 9, 20, 2, 13, 7, 18, 5, 16, 10, 21, 1, 12, 7, 18, 4, 15]
>>> len(set(van_der_corput_index(seq)))
21
>>> from collections import Counter
>>> 
>>> for listlen in (2, 3, 5, 7, 11, 13, 17, 19, 23,
        29, 31, 37, 41, 43, 47, 53, 59, 61,
        67, 71, 73, 79, 83, 89, 97, 1023,
        1024, 4095, 4096, 2**16 - 1, 2**16):
    out = list(van_der_corput_index( list(range(listlen) )))
    outcount = Counter(out)
    if outcount and outcount.most_common(1)[0][1] > 1:
        print("Duplicates in %i leaving %i unique nums." % (listlen, len(outcount)))
    outlen = len(out)
    if outlen != listlen:
        print("Length change in %i to %i" % (listlen, outlen))


Duplicates in 23 leaving 21 unique nums.
Duplicates in 43 leaving 37 unique nums.
Duplicates in 47 leaving 41 unique nums.
Duplicates in 53 leaving 49 unique nums.
Duplicates in 59 leaving 55 unique nums.
Duplicates in 71 leaving 67 unique nums.
Duplicates in 79 leaving 69 unique nums.
Duplicates in 83 leaving 71 unique nums.
Duplicates in 89 leaving 81 unique nums.
>>> outlen
65536
>>> listlen
65536
>>>