Iterate attraverso un numero dinamico di loop for (Python)

Question

Sto usando python per ordinare alcuni numeri. Vorrei creare una funzione che mi permetta di inserire un valore (4, 8, 16, 32, 64, ecc.), Creare una serie di numeri e riorganizzare la loro sequenza.

Sono figure che dettaglio come determinare la sequenza di valore = 4 e 8.

Per valore = 4 matrice (x = [0, 1, 2, 3]) dovrebbe essere diviso aggiunto in due ([0,1] e [2,3]) e poi combinati in base al primo numero in ciascun array ([0, 2, 1, 3]).

Per valore = 8 della matrice (x = [0, 1, 2, 3, 4, 5, 6, 7]) dovrebbe essere diviso in due ([0, 1, 2, 3 ] e [4, 5, 6, 7]). Entrambi gli array devono essere nuovamente divisi in due ([0, 1, 2, 3] in [0,1] e [2,3] e [4, 5, 6, 7] in [4,5] e [6, 7]). Quindi gli array dovrebbero essere combinati in base al primo numero di ciascun array e alla sequenza del secondo set di matrici ([0, 4, 2, 6, 1, 5, 3, 7]).

Non so come gestire la ricorsione (nidificato in modo dinamico per i cicli). Sto provando a passare in rassegna ogni brach che è stato creato dividendo la matrice. Ho esaminato itertools e ricorsione (Function with varying number of For Loops (python)), ma non sono riuscito a farlo funzionare. Sotto, ho aggiunto il codice per illustrare il mio approccio fino ad ora.

Qualsiasi aiuto è molto apprezzato. Sono anche aperto ad altre idee per determinare la sequenza.

Sto usando python 2.7.6 e numpy.

Codice:

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) 

uscita:

[0, 2, 1, 3] 

Codice:

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) 

uscita:

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

L'uscita per valore = 16 deve essere [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7 15].

Answer 1

Ecco un modo NumPythonic utilizzando np.transpose e 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() 

prega di notare che .transpose(np.arange(len(shp))[::-1] semplificherebbe a .T, così avremmo una versione semplificata -

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

È possibile semplificare ulteriormente e sostituire trasporre del tutto eseguendo il ravel/flattening in un ordine di colonna maggiore come in fortran con .ravel('F') di condurci infine a -

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

piste del campione -

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

Il modo più semplice per farlo è quello di non uso cicli for, ma per fare un po 'la gestione di array con 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]) 

Quello che fa è riconfigura x in una matrice dimensionale n dove n è la potenza di 2 che corrisponde alla lunghezza di x. Dopo questo rimodellamento, la lunghezza di ogni dimensione è 2. Quindi invertiamo tutte le dimensioni e appiattiamo per ottenere l'array desiderato.

Modifica

Si tratta di un approccio simile a Divakar's Solution, e ha finito per fare molto più conciso, ma mi limiterò a lasciare questo qui per i posteri.

Answer 3

La versione ricorsiva pitone, per chiarezza:

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 

per

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

Oppure, osservando la rappresentazione binaria del risultato, una soluzione NumPy:

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