1

問題：
Pを、文字列を隣接する、場合によってはnullの部分文字列に分割するすべての可能な方法のセットとします。この問題を解決するための洗練されたアルゴリズムを探しています。

背景コンテキスト：
文字列（s、w）のタプルが与えられた場合、上記のようにP（s）とP（w）を定義します。サブストリングLevenshtein（挿入、削除、および置換）編集の数が最小になる特定のパーティションR∈P（s）およびT∈P（w）が存在します。

例：
文字列 "foo"を5つのサブ文字列に分割します。ここで、εはnullサブ文字列です。

[ε, ε, f, o, o]  
[ε, f, ε, o, o]  
[ε, f, o, ε, o]  
[ε, f, o, o, ε]

[f, ε, ε, o, o]  
[f, ε, o, ε, o]  
[f, ε, o, o, ε]

[f, o, ε, ε, o]  
[f, o, ε, o, ε]

[f, o, o, ε, ε]
4

1 に答える 1

1

単純な再帰的アプローチはどうですか?

def part(s, n, pre):
    if s == '':
        return [pre + '.' * n]
    elif n > 0:
        res = []
        if n > len(s):
            res += part(s, n-1, pre + '.')
        if len(s) > 0:
            res += part(s[1:], n-1, pre + s[0])
        return res

結果：

>>> print part('foo', 5, '')
['foo..', 'fo.o.', 'fo..o', 'f.oo.', 'f.o.o', 'f..oo', '.foo.', '.fo.o', '.f.oo', '..foo']
于 2012-09-17T13:28:53.327 に答える