Iterate durch eine dynamische Anzahl von for-Schleifen (Python)

Question

Ich benutze Python, um einige Zahlen zu sequenzieren. Ich möchte eine Funktion erstellen, die es mir erlaubt, einen Wert einzugeben (4, 8, 16, 32, 64, usw.), ein Array von Zahlen zu erstellen und ihre Reihenfolge neu zu ordnen.

Ich habe Zahlen gegeben, die ausführlich, wie die Sequenz, die für Wert bestimmen = 4 und 8.

Für Wert = 4 das Array (x = [0, 1, 2, 3]) aufgespalten werden soll in zwei ([0,1] und [2,3]) und dann kombiniert basierend auf der ersten Zahl in jedem Array ([0, 2, 1, 3]).

Für Wert = 8 das Array (x = [0, 1, 2, 3, 4, 5, 6, 7]) in zwei aufgeteilt werden ([0, 1, 2, 3 ] und [4, 5, 6, 7]). Beide Arrays sollten wieder in zwei Teile aufgeteilt werden ([0, 1, 2, 3] in [0,1] und [2,3] und [4, 5, 6, 7] in [4,5] und [6], 7]). Dann sollten die Arrays basierend auf der ersten Nummer in jedem Array und der Sequenz des zweiten Satzes von Arrays ([0, 4, 2, 6, 1, 5, 3, 7]) kombiniert werden.

Ich weiß nicht, wie die Rekursion zu handhaben (dynamisch für Schleifen verschachtelt). Ich versuche, jeden Bruch, der durch das Teilen des Arrays erzeugt wird, zu durchlaufen. Ich habe in itertools und Rekursion (Function with varying number of For Loops (python)) untersucht, aber ich konnte es nicht arbeiten lassen. Im Folgenden habe ich einen Code hinzugefügt, der meinen bisherigen Ansatz veranschaulicht.

Jede Hilfe wird sehr geschätzt. Ich bin auch offen für andere Ideen, um die Reihenfolge zu bestimmen.

Ich benutze Python 2.7.6 und 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) 

Ausgang:

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

Ausgang:

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

Der Ausgang für Wert = 16 sollte [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] sein.

Answer 1

Hier ist ein NumPythonic Art und Weise mit np.transpose und 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() 

Bitte beachten Sie, dass .transpose(np.arange(len(shp))[::-1]-.T vereinfachen würde, so würden wir eine vereinfachte Version haben -

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

Sie können weiter vereinfachen und ersetzen die Transponierte insgesamt durch die ravel/flattening in einer Spalte-Major-Reihenfolge wie in fortran mit .ravel('F') uns schließlich zu führen -

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

Beispielläufe -

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

Der einfachste Weg, dies zu tun ist, um nicht Verwendung für Schleifen, aber einige Array-Bearbeitung mit numpy zu tun.

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

Was dies tut, ist es in eine xn -dimensionalen Array umformt n wo die Potenz von 2 ist, die auf die Länge des x entspricht. Nach dieser Umformung beträgt die Länge jeder Dimension 2. Wir kehren dann alle Dimensionen um und glätten, um das gewünschte Array zu erhalten.

bearbeiten

Dies ist ein ähnlicher Ansatz Divakar's Solution, und er endete knapp tun es viel mehr, aber ich werde dies nur hier für die Nachwelt hinterlassen.

Answer 3

Die rekursive Python-Version, für Klarheit:

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 

für

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

Oder die binäre Darstellung des Ergebnisses zu beobachten, eine numpy Lösung:

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