レベルキャッシュなしでアレンジメントにハンドラーを適用しますか?

質問内容

順列全体を返さずに、指定されたハンドラーをすべての入力順列に適用する関数を作成したいと考えています。

＃＃＃コード＃＃＃

(

go 内)

アレンジメントを見つける:
• リーリー

テストケース
• (単純)

  : リーリー

イラスト

上記の関数

findallpermutationapplyhandler()
• は、順列を検索し、指定されたハンドラーを各組み合わせに適用できます。
ただし、
• 以前の n-1 レベル (最新の 2 レベルを同時に) をキャッシュする必要があります。 最終
レベルに依存するレベルはもうないため、
• 最終 レベルのキャッシュを回避しました。
＃＃＃質問＃＃＃

最後の 2 レベルのキャッシュを回避することは可能ですか?
• 1. (別名、空間の複雑さを o(1)

     または o(n) にするか、あるいは o(n^2) のほうが良いと思います）。 。

しかし、レベル
• i
  はレベル
  1. i-1 に基づいているため、それは不可能に思えます。
もしそうなら、空間の複雑さを軽減するためのより良いアルゴリズムはありますか? (再帰ではなく) 反復が推奨されます。

正解

Panditaアルゴリズム

をお探しのようですね これは、配列のすべての順列を辞書順に反復処理する簡単な方法です。

ただし、配列の要素を並べ替えることができる必要があります。そうでない場合 (ジェネリック型であるため)、すべての配列インデックスの補助配列を作成し、それらの順列を生成できます。

以上がレベルキャッシュなしでアレンジメントにハンドラーを適用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。