Iterate through a dynamic number of for loops (Python)

Question

I am using python to sequence some numbers. I would like to create a function which allows me to input a value (4, 8, 16, 32, 64, etc.), create an array of numbers, and rearrange their sequence.

I've added figures which detail how to determine the sequence for value = 4, and 8.

For value = 4 the array (x = [0, 1, 2, 3]) should be split in two ([0,1] and [2,3]) and then combined based on the first number in each array ([0, 2 ,1 ,3]).

For value = 8 the array (x = [0, 1, 2, 3, 4, 5, 6, 7]) should be split into two ([0, 1, 2, 3] and [4, 5, 6, 7]). Both arrays should be split in two again ([0, 1, 2, 3] into [0,1] and [2,3] and [4, 5, 6, 7] into [4,5] and [6,7]). Then the arrays should be combined based on the first number in each array and the sequence of 2nd set of arrays ([0, 4, 2, 6, 1, 5, 3, 7]).

I don't know how to handle the recursion (dynamically nested for loops). I am trying to loop through each brach that is created by spliting the array. I've looked into itertools and recursion (Function with varying number of For Loops (python)), but I could not make it work. Below, I've added code to illustrate my approach thus far.

Any help is much appreciated. I am also open to other ideas to determine the sequence.

I am using python 2.7.6 and numpy.

Code:

import numpy
value = 4
a = []
x = numpy.arange(value)
y = numpy.array_split(x, 2)
for i in range(2):
    for j in y:
        a.append(j.tolist()[i])
print(a)

Output:

[0, 2, 1, 3]

Code:

import numpy
value = 8
a = []
x = numpy.arange(value)
y = numpy.array_split(x, 2)
for i in range(2):
    for h in range(2):
        for j in y:
        z = numpy.array_split(j, 2)
                a.append(z[h][i])
    print(a)

Output:

[0, 4, 2, 6, 1, 5, 3, 7]

The output for value = 16 should be [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11 ,7 15].

Answer 1

Here's a NumPythonic way using np.transpose and reshaping -

def seq_pow2(N):
    shp = 2*np.ones(np.log2(N),dtype=int)
    return np.arange(N).reshape(shp).transpose(np.arange(len(shp))[::-1]).ravel()

Please note that .transpose(np.arange(len(shp))[::-1] would simplify to .T, so we would have a simplified version -

def seq_pow2(N):
    shp = 2*np.ones(np.log2(N),dtype=int)
    return np.arange(N).reshape(shp).T.ravel()

You can further simplify and replace the transpose altogether by doing the ravel/flattening in a column-major ordering like in fortran with .ravel('F') to lead us finally to -

def seq_pow2(N):
    shp = 2*np.ones(np.log2(N),dtype=int)
    return np.arange(N).reshape(shp).ravel('F')

Sample runs -

In [43]: seq_pow2(4)
Out[43]: array([0, 2, 1, 3])

In [44]: seq_pow2(8)
Out[44]: array([0, 4, 2, 6, 1, 5, 3, 7])

In [45]: seq_pow2(16)
Out[45]: array([ 0,  8,  4, 12,  2, 10,  6, 14,  1,  9,  5, 13,  3, 11,  7, 15])

Answer 2

The python recursive version, for clarity :

def rec(n):
    if n==1 : return [0]
    l=[0]*n
    l[::2]=rec(n//2)
    for i in range (0,n,2) : l[i+1]=l[i]+n//2
    return l

for

In [6]: rec(16)
Out[6]: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Or, observing the binary representation of the result, a numpy solution :

def rearange(N):
    u=2**arange(N.bit_length()-1)
    v=arange(N)
    bits= u[None,:] & v[:,None]
    return sum(bits*u[::-1],1)

Answer 3

The easiest way to do this is to not use for loops but to do some array manipulation with numpy.

N = 8
pow2 = np.log2(N)
out = np.arange(N).reshape([2]*pow2).transpose(np.arange(pow2)[::-1]).flatten()   

   array([0, 4, 2, 6, 1, 5, 3, 7])

What this does is it reshapes x into a n-dimensional array where n is the power of 2 that corresponds to the length of x. After this reshaping, the length of each dimension is 2. We then reverse all of the dimensions and flatten to get the array you want.

Edit

This is a similar approach to Divakar's Solution, and he ended up doing it much more concisely, but I'll just leave this here for posterity.