リストのリスト（ここでは最大で1つのレベルでネストされています）を考えると、特有の問題：
[['a', 'b'], 'c', ['d', 'e'], ['f', 'g'], 'h']
..指定されたリストと同じ長さのすべてのリストを見つけ、サブリストからの要素のすべての可能な組み合わせを含み、元のサブリストと同じ位置に指定されたサブリストの要素が1つだけある(これを言葉で表現することさえ難しい)。つまり、これを見つけます：
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'e', 'f', 'h']
['a', 'c', 'e', 'g', 'h']
['b', 'c', 'd', 'f', 'h']
['b', 'c', 'd', 'g', 'h']
['b', 'c', 'e', 'f', 'h']
['b', 'c', 'e', 'g', 'h']
今、私は解決策を見つけましたが、それは私にとって満足のいくものではありません:
def all_paths(s, acc=None, result=None):
# not using usual "acc = acc or []" trick, because on the next recursive call "[] or []" would be
# evaluated left to right and acc would point to SECOND [], which creates separate accumulator
# for each call stack frame
if acc is None:
acc = []
if result is None:
result = []
head, tail = s[0], s[1:]
acc_copy = acc[:]
for el in head:
acc = acc_copy[:]
acc.append(el)
if tail:
all_paths(tail, acc=acc, result=result)
else:
result.append(acc)
return result
ご覧のとおり、アキュムレータ リストを 2 回コピーする必要があります。これは、.append() または .extend() メソッドが再帰スタックで呼び出された場合、アキュムレータがラベルによって渡されるため変更されるという明らかな理由からです (公式用語での共有)。 ?)。
アキュムレータから pop() と append() で関連するアイテム数を取得するソリューションを作成しようとしましたが、正しく取得できません。
def all_p(s, acc=None, result=None, calldepth=0, seqlen=0):
if acc is None:
acc = []
if result is None:
seqlen = len(s)
result = []
head, tail = s[0], s[1:]
for el in head:
acc.append(el)
if tail:
all_p(tail, acc=acc, result=result, calldepth=calldepth+1, seqlen=seqlen)
else:
result.append(acc[:])
print acc
for i in xrange(1+seqlen-calldepth):
acc.pop()
return result
結果：
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'g', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'h']
['a', 'c', 'd', 'e', 'b', 'c', 'd', 'e', 'g', 'h']
明らかに、これは、ここでの深さ優先再帰が呼び出しチェーンを上下にジャンプし、pop() の数を正しく取得してアキュムレータ リストを微調整できないためです。
リストのコピーはO(n)であり、リストからk個のアイテムをポップするのはO(k)であるため、これはほとんど実用的ではないことを認識しています。したがって、ここではそれほど大きな違いはありませんが、達成することができます。
(背景: phonecode ベンチマークhttp://page.mi.fu-berlin.de/prechelt/phonecode/をやり直しています。これはすべての単語を検索する部分ですが、電話番号の各部分は次のようないくつかの単語:
... '4824': ['fort', 'Torf'], '4021': ['fern'], '562': ['mir', 'Mix'] ...
そのため、特定の電話番号に対応する、一致する単語および/または数字の選択されたリストを通じて、可能なすべての「パス」を見つける必要があります)
ご質問、ご要望：
アキュムレータをコピーしないバージョンを修正できますか?
itertools モジュールを使用するこれに対する解決策はありますか?
この特定の問題に対する他のより良いアプローチはありますか? 非再帰的なソリューション、より高速なソリューション、メモリ集約型のソリューションのようなものですか?
はい、これが大量の問題であることはわかっていますが、誰かがそれらの空でないサブセットを解決してくれれば、私は感謝します。:-)