配列内のすべての可能性を降順の値で列挙します。

Question

私は、要素がすべて1に降りることができる任意の長さの配列のすべての可能な値を列挙する再帰的なアプローチを書こうとしています。より正式には、A_1、A_2、...、A_Nの要素を持つ配列Aと、B_1、B_2 ... B_Nの配列Bが与えられているとします。 A_iとB_iとの間には関係がある。ここで、iは1とNとの間にあり、A_iは1とB_iの間にある。そのような配列のセットの場合、A_iのすべての可能な状態を見つけたいと思います。例えば

、配列[1 2 3]以下の6つの可能な状態があります

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

[1 2]生成することになる[1 1]、[1 2]など

を

私のようなPythonで解決策を試してみた：

b = [1, 3, 3] 
n = len(b) 

a = [] 
k = 0 
r = 0 

print b 
print '------' 

def f(i, k, a, r): 
    k += 1 
    if i == n-1: 
    return False 
    for j in range(1, b[i+1]+1): 
    r += 1 
    print "i: %d b[i]: %d k: %d new: %d r: %d" % (i, b[i], k, j, r) 
    f(i+1, k, a, r) 

f(0, k, a, r) 

が、私は右の値を取得するように見えることができないと私はデータ構造を移入することができません。例えば[3,3]は唯一の3つのノードまたは結果とツリー生成します。私は問題を通して考えるためにこれをやっているので

[3, 3] 
------ 
i: 0 b[i]: 3 k: 1 new: 1 r: 1 
i: 0 b[i]: 3 k: 1 new: 2 r: 2 
i: 0 b[i]: 3 k: 1 new: 3 r: 3 

を、私はどのように好奇心：

• Pythonのitertools問題をより効率的

私のアプローチを考えるどのよう

のこの家族について話すのリンク

これが可能になるかもしれません10

感謝しています。

Answer 1

基本的にすべての列に対して、「許可」値のセットがあります。これらの各セットから値を選択し、関連する列に入れることで、有効な「関連」配列が生成されます。あなたはすべての可能性を試す必要があります。

再帰的に問題を小さくする必要があります。

def enumerate(v):                
    if len(v) == 0:                
     yield v                 
    else:                  
     for i in range(1, v[0] + 1):            
      for rest in enumerate(v[1:]):          
       yield [i] + rest             

そして、あなたが明示的な再発と、itertoolsと同じ効果を持つことができます：あなたはここで、配列の長さに再帰的かもしれ

def enumerate2(v):                
    from itertools import product            
    return product(*(range(1, e+1) for e in v)) 

Answer 2

あなたが探している機能/ツールは、itertoolsを含む多くの場所で実装されている "デカルト製品"と呼ばれています。

itertools.productは（*イテラブル[リピート]）

また、これは便利かもしれません：link

はあなたの最終的な目標を達成するために、あなたが必要なもの、いわゆる "辞書編集" ソートです。私はそれが解決された問題（多くの恣意的なソートルールに依存する）であるかどうかわからないので、使いやすいツールがあるかどうかはわかりません。しかし、lexicographical出力についてはhintsなので、Pythonのドキュメントを見ることができます。