-1

私が書いたコードは、T(N) = T(N-1)*N + O((N-1!)*N) を取得している実行時間とスペースの漸近的な尺度では見栄えが悪いようです。入力のサイズ。最適化するためのアドバイスが必要です

これはアルゴリズムベースのインタビューの質問であるため、ライブラリを使用せずに最も効率的な方法でロジックを実装する必要があります

これが私のコードです

def str_permutations(str_input,i):
    if len(str_input) == 1:
        return [str_input]
    comb_list = []
    while i < len(str_input):
        key = str_input[i]
        if i+1 != len(str_input):
            remaining_str = "".join((str_input[0:i],str_input[i+1:]))
        else:
            remaining_str = str_input[0:i]
        all_combinations = str_permutations(remaining_str,0)
        for index,value in enumerate(all_combinations):
            all_combinations[index] = "".join((key,value))
        comb_list.extend(all_combinations)
        i = i+1
    return comb_list
4

2 に答える 2

2

質問へのコメントで述べたように、一般的なケースでは、指数関数的な複雑さを下回ることはありません。これは、n個別の文字の場合n!、入力文字列の順列があり、O(2 n ) が O(n!) のサブセットであるためです。 .

以下では、一般的なケースの漸近的な複雑さを改善することはできませんが、複数回出現する文字を含む文字列のすべての順列を生成するブルート フォース アプローチを最適化できます。たとえば、文字列daedoid; 6 = 3!やみくもにすべての順列を生成すると、が 3 回出現するため、すべての順列時間が得られますd。最初に同じ文字の複数回の出現を排除し、代わりに各文字の使用頻度を覚えておくことで、これを回避できます. したがって、ck c回出現する文字がある場合、k cを節約できます。順列。したがって、合計すると、これにより「すべての c に対して k cを超える製品」の係数が節約されます。

于 2013-03-28T20:22:36.333 に答える
0

独自に記述する必要がない場合は、 および を参照itertools.permutationsしてくださいcombinations。

于 2013-03-28T17:40:18.833 に答える