1

n次元の最長共通部分列を実装しています。現在の問題：n個の文字列をトラバースするにはどうすればよいですか？n個のループが必要なため、ループをネストするだけforでは機能しなくなります。その問題の良い解決策は何ですか？ループ+再帰だと思いますが、正確にはどのくらいですか？私は完全なアルゴリズムを求めているのではなく、動的計画法アルゴリズムのすべての組み合わせを生成する方法だけを求めています。2Dの例：

for position, char in word0:
  for position1, char1 in word1:
    # code here
4

2 に答える 2

2

再帰的に実行したくない場合は、次nのようにネストされた「for」ループを実装できます（ただし、「for」ループは文字通りforループではなくなりました）。

iインデックスの配列です。
mそれぞれの上限の配列はi
iiインデックスのiインデックスです（range(n)）

n=4 # just an example
m=[3 for ii in range(n)] # just an example

i=[0 for ii in range(n)]
while True:
  print " ".join(["%2d"%x for x in i])
  for ii in range(n-1,-1,-1):
    i[ii] +=1
    if i[ii]<m[ii]: break # index i[ii] has not yet reached its individual max. value
    i[ii] = 0
  if sum(i)==0: break # all indices have counted to max. value
于 2011-12-08T14:21:01.317 に答える
1

これは、たとえば0000から9999までのカウントに似ています。これは、それぞれ10文字の4つの単語に対応します。0000-> 0001-> 0002-> ...-> 0009->0010->...各段階で最後の桁を増やし、ロールオーバーしたときに前の桁を増やします。最初の桁がロールオーバーするまで、完了します。

カウントをイテレータにカプセル化する1つの方法は次のとおりです。

def count(limits):
    idcs = [0] * len(limits)
    while True:
        yield tuple(idcs)
        for n in range(len(limits)-1, -1, -1):
            idcs[n] += 1
            if idcs[n] != limits[n]:
                break
            elif n == 0:
                raise StopIteration
            else:
                idcs[n] = 0

words = ['foo', 'bar', 'xyzzy']
for idcs in count(map(len, words)):
    chars = map(lambda w, i: w[i], words, idcs)
    print idcs, chars
于 2011-12-08T15:36:36.157 に答える