Iterate over an array in a certain order, so that

Question

I want to iterate over an array in a certain fashion:
Starting with the first and the last element of the array, the next element I want to visit is the one furthest from all previously visited elements.

For an array of length n+1, the sequence would be

• 0,
• n,
• n/2 (furthest from 0 and n),
• n/4 and n*3/4 (furthest from all 3 previous indices),
• n/8, n*3/8, n*5/8, n*7/8, (furthest from all 5 previous indices)
• n*1/16, n*3/16, n*5/16, n*7/16, n*9/16, n*11/16, n*13/16, n*15/16
• ...

if n is not a power of two, then some of these numbers will have to be rounded up or down, but I am not sure how to avoid duplicates when rounding.

At the end I want an integer sequence that contains all the numbers between 0 and n exactly once. (For any n, not just powers of two)

Is there a name for this permutation?

How would a function that generates these numbers work?

I am looking for a function that can generate these numbers on-the-fly.

If there are a billion elements, I do not want to manage a giant list of all previously visited elements, or generate the whole permutation list in advance.

The idea is that I can abort the iteration once I have found an element that fits certain criteria, so I will in most cases not need the whole permutation sequence.

So I am looking for a function f(int currentIndex, int maxIndex) with the following properties:

To interate over an array of size 8, i would call

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

(I am not quite sure how to extend this example to numbers that are not a power of two)

Is there a function with these properties?

Answer 1

I see how to do this, but it's tricky to describe.. bear with me.

The key idea is to logically partition your array into two sets: One contains a number of elements equal to the greatest power of two still less than the size of the array, and the other contains everything else. (So, if your array holds 29 elements, you'd have one with 16 and the other with 13.) You want these to be mixed as fairly as possible, and you want:

1. A function to find the "Real" index of the i-th element of the first logical set (equivalently: How many elements of the second set come before the i-th element of the first set)
2. A function to tell you whether some index i belongs to the first or second logical set.

You then run the "Ideal" function you described over the first set (mapping with function 1, above), then do a single pass over the remaining elements. So long as you distribute fairly between the logical set, this will do as you describe.

To (logically) describe which indices belong to which partition: Call the size of the first logical partition k and the size of the second partition j. Assume that every element of the first set has j/k units of "credit" associated with it. Begin filling the true array with elements of the logical array, adding up credit as you go, but every time you would get to more than one unit of credit, place an element from the second array instead, and reduce the stored credit by one. This will fairly distribute exactly j elements from the second array between k elements of the first array. NOTE: You don't actually perform this calculation, it's just a logical definition.

With a little arithmetic, you can use this to implement the functions I described above. Before the i-th element of the first set will be exactly floor(i * j/k) elements of the second set. You only run the second function during the final pass, so you can run that exactly from the definition.

Does this make sense? I'm sure this will work, but it's difficult to describe.

Answer 2

Could you not use an array such that array[n][i]

such that

Array [0][i] = "1,2,3,4,5,6,7" 'start
Array [1][i] = "1,2,3,4" '1st gen split 1
Array [2][i] = "4,5,6,7" '1st gen split 2
Array [3][i] = "1,2" '2nd gen split 1 split 1
Array [4][i] = "3,4" '2nd gen split 1 split 2
Array [5][i] = "4,5" '2nd gen split 2 split 1
Array [6][i] = "6,7" '2nd gen split 2 split 1

'use dynamic iteration such that you know the size going into the array i.e. nextGen=Toint(Ubound(Array)/2)

If(
   last(Array[n][i]) = first(Array[n+1][i] 
   then Pop(Array[n+1][i])
)

Answer 3

I was able to solve this myself, with the tips given by Paddy3118 and Edward Peters.

I now have a method that generates a Van der Corput permutation for a given range, with no duplicates and no missed values, and with constant and negligible memory requirements and good performance.

The method uses a c# iterable to generate the sequence on the fly.

The method VanDerCorputPermutation() takes two parameters, the upper exclusive bound of the range, and the base that should be used for generating the sequence. By default, base 2 is used.

If the range is not a power of the given base, then the next larger power is used internally, and all indices that would be generated outside the range are simply discarded.

Usage:

Console.WriteLine(string.Join("; ",VanDerCorputPermutation(8,2)));
// 0; 4; 2; 6; 1; 3; 5; 7

Console.WriteLine(string.Join("; ",VanDerCorputPermutation(9,2)));
// 0; 8; 4; 2; 6; 1; 3; 5; 7

Console.WriteLine(string.Join("; ",VanDerCorputPermutation(10,3)));
// 0; 9; 3; 6; 1; 2; 4; 5; 7; 8 

Console.WriteLine(VanDerCorputPermutation(Int32.MaxValue,2).Count());
// 2147483647 (with constant memory usage)

foreach(int i in VanDerCorputPermutation(bigArray.Length))
{
     // do stuff with bigArray[i]
}

for (int max = 0; max < 100000; max++)
{
    for (int numBase = 2; numBase < 1000; numBase++)
    {
        var perm = VanDerCorputPermutation(max, numBase).ToList();
        Debug.Assert(perm.Count==max);
        Debug.Assert(perm.Distinct().Count()==max);
    }
}

The code itself uses only integer arithemtic and very few divisions:

IEnumerable<int> VanDerCorputPermutation(int lessThan, int numBase = 2)
{
    if (numBase < 2) throw new ArgumentException("numBase must be greater than 1");

    // no index is less than zero
    if (lessThan <= 0) yield break;

    // always return the first element
    yield return 0;

    // find the smallest power-of-n that is big enough to generate all values
    int power = 1;
    while (power < lessThan / numBase + 1) power *= numBase;

    // starting with the largest power-of-n, this loop generates all values between 0 and lessThan 
    // that are multiples of this power, and have not been generated before.
    // Then the process is repeated for the next smaller power-of-n
    while (power >= 1)
    {
        int modulo = 0;
        for (int result = power; result < lessThan; result+=power)
        {
            if (result < power) break; // overflow, bigger than MaxInt

            if (++modulo == numBase)
            {
                //we have used this result before, with a larger power 
                modulo = 0;
                continue;
            }

            yield return result;
        }
        power /= numBase; // get the next smaller power-of-n
    }
}

Answer 4

Yes, it is called partitioning.
It is a very common methodology for searching in an ordered array.
also, it is used by QuickSort algorithm.

it mostly being implemented as a Recursive function that samples the "center" element, and then recurse on the "left" collection, then the "right" collection.
if the array is of length 1, sample it and don't recurse.

in the following example, i just search the array in the order you describe,
if the array was ordered, after checking the first pivot, i would have skipped checking the RightPart, or the LeftPart depending on the pivot value.

int partition(int* arr, int min, int max, int subject) 
{ // [min, max] inclusive!
    int pivot = (max - min + 1) >> 1; // (max - min)/2
    if(arr[pivot] == subject)
        return pivot;

    if(pivot > 0) 
    {
        int leftPart = partition(arr, min, pivot - 1, subject);
        if(leftPart >= 0)
            return leftPart;
    }

    if(max - pivot > 0) 
    {
        int rightPart = partition(arr, pivot + 1, max, subject);
        if(rightPart >= 0)
            return rightPart;
    }

    return -1; // not found
}

int myArr[10] = {4,8,11,7,2,88,42,6,5,11 };
int idxOf5 = partition(myArr, 0, 9, 5);

Answer 5

The hopping about you describe is a feature of the Van der Corput sequence, as mentioned in a task I wrote on Rosetta Code.

I have an exact function to re-order an input sequence, but it needs arrays as large as the input array.

What follows is an approximate solution that yields indices one by one and only takes the length of the input array, then calculates the indices with constant memory.

The testing gives some indication of how "good" the routine is.

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