アレイの隣接パワーセットを計算する

Question

インターネットはfull of powerset algorithmsです。

私の場合、私は隣接する部品のパワーセットだけが必要です。

例： From：[1, 2, 3]、私が取得する必要があるでしょう：

adjacentPowerset([1, 2, 3]) = [[1, 2, 3], [1, 2], [2, 3], [1], [2], [3]]; 
// Without [1, 3] 

私はこれを達成するために苦労しています...

機能液がはるかに高く評価されるだろう（最終的には再帰的）。

Answer 1

空でない範囲がi<jxs[i:j]のように見えます。

あなたはこのためにネストされたループを使用することができます。

def adj_powerset(xs): 
    for i in xrange(len(xs)): 
     for j in xrange(i, len(xs)): 
      yield xs[i:j+1] 

print list(adj_powerset([1, 2, 3])) 

出力：

[[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]] 

Answer 2

あなたはこの問題を解決するためのウィンドウをスライディング使用することができます。

のpythonコード：

def adjacent_powerset(arr): 
    result = [] 

    #loop over all possible lengths of subarrays 
    for i in range(1, len(arr) + 1): 
     #loop over all possible starting indices of subarrays of length i 
     for j in range(1, len(arr) - i + 1): 
      #store subarray at position j with length i in the powerset 
      result.append(arr[j:j+i]) 

    return result 

テスト・ラン：

print adjacent_powerset([1, 2, 3, 4]) 

が生成

[[1] [1,2,3]、[2,3,4]、[1,2,3]、[1,2,3]、[1,2,3] 2,3,4 ]]

あなたが大きいものから小さいサブセットに秩序を好む場合は、この行を交換する必要があります。

for i in range(1, len(arr) + 1): 

によって

for i in range(len(arr) , 0, -1): 

基本的な考え方は、Aのすべてのサブアレイだろう長さがlのスライディングウインドウを使用して特定の長さlを生成し、スライディングウインドウの内容を結果にコピーすることができます。

Answer 3

Pythonで再帰的なソリューション -

st = set() 

arr = [1, 2, 3] 

res = list() 

def power_set(i, j): 
    if i == j: 
     return 
    if (i, j) not in st: 
     res.append(arr[i : j]) 
    power_set(i, j - 1) 
    power_set(i + 1, j) 
    st.add((i, j)) 

power_set(0, len(arr)) 

print(res) 

出力 -

[[1, 2, 3], [1, 2], [1], [2], [2, 3], [3]]