通過動態循環迭代（Python）

Question

我正在使用python對一些數字進行排序。我想創建一個函數，它允許我輸入一個值（4,8,16,32,64等），創建一個數組數組，並重新排列它們的序列。

我已經添加數字如何確定值= 4的序列，其細節和8

對於值= 4陣列（X = [0，1，2，3]）應當被拆分在兩個（[0,1]和[2,3]）中，然後根據每個數組中的第一個數字（[0,2,1,3]）進行組合。

對於值= 8陣列（X = [0，1，2，3，4，5，6，7]）應被分成兩個（[0，1，2，3 ]和[4，5，6，7]）。兩個數組應該再次分成兩部分（[0,1,2,3]分爲[0,1]和[2,3]和[4,5,6,7]分爲[4,5]和[6， 7]）。然後根據每個數組中的第一個數字和第二組數組的順序（[0,4,2,6,1,5,3,7]）組合數組。

我不知道如何處理遞歸（動態嵌套的循環）。我試圖循環通過拆分數組創建的每個布爾。我研究過itertools和遞歸（Function with varying number of For Loops (python)），但我無法使它工作。下面，我添加了代碼來說明迄今爲止我的方法。

任何幫助，非常感謝。我也接受其他想法來確定序列。

我使用python 2.7.6和numpy。

代碼：

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) 

輸出：

[0, 2, 1, 3] 

代碼：

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) 

輸出：

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

value = 16的輸出應該是[0,8,4,12,2,10,6,14,1,9,5,13,​​3,11,7,15]。

Answer 1

下面是使用np.transpose和reshaping一個NumPythonic方式 -

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

請注意，.transpose(np.arange(len(shp))[::-1]將簡化爲.T，所以我們將有一個簡化版本 -

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

可以進一步簡化和替換轉置一起做ravel/flattening在列主要排序像fortran與.ravel('F')最終導致我們 -

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

樣品試驗 -

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

要做到這一點是不使用 for循環，但做一些數組操作與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]) 

這樣做是它重塑x成n維陣列，其中n爲2對應於的x長度的功率。在這個整形之後，每個維度的長度都是2.然後我們扭轉所有維度並將其平坦化以得到您想要的數組。

編輯

這是一個類似的方法來Divakar's Solution，和他結束了簡明得多做這件事，但我就離開這個位置留給後人。

Answer 3

蟒蛇遞歸版本，爲了清楚：

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 

爲

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

或者，觀測結果的二進制表示，一個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)